#P2574. XOR的艺术
XOR的艺术
题目描述
AKN 觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下:
- 拥有一个伤害串,是一个长度为 的只含字符
0
和字符1
的字符串。规定这个字符串的首字符是第一个字符,即下标从 开始。 - 给定一个范围 ,伤害为伤害串的这个范围内中字符
1
的个数。 - 会修改伤害串中的数值,修改的方法是把 中所有原来的字符
0
变成1
,将1
变成0
。
AKN 想知道一些时刻的伤害,请你帮助他求出这个伤害。
输入格式
输入的第一行有两个用空格隔开的整数,分别表示伤害串的长度 ,和操作的个数 。
输入第二行是一个长度为 的字符串 ,代表伤害串。
第 到第 行,每行有三个用空格隔开的整数 。代表第 次操作的方式和区间,规则是:
- 若 ,则表示将伤害串的 区间内的
0
变成1
,1
变成0
。 - 若 ,则表示询问伤害串的 区间内有多少个字符
1
。
输出格式
对于每次询问,输出一行一个整数,代表区间内 1
的个数。
10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6
3
6
1
提示
样例输入输出 解释
原伤害串为 1011101001
。
对于第一次操作,改变 的字符,伤害串变为 1100101001
。
对于第二次操作,查询 内 1
的个数,共有 个。
对于第三次操作,改变 的字符,伤害串变为 1111010001
。
对于第四次操作,查询 内 1
的个数,共有 个。
对于第五次操作,改变 的字符,伤害串变为 0000010001
。
对于第六次操作,查询 内 1
的个数,共有 个。
数据范围与约定
对于 的数据,保证 。
另有 的数据,保证 。
对于 的数据,保证 ,,, 中只含字符 0
和字符 1
。