#P2574. XOR的艺术

XOR的艺术

题目描述

AKN 觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下:

  1. 拥有一个伤害串,是一个长度为 nn 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符,即下标从 11 开始。
  2. 给定一个范围 [l, r][l,~r],伤害为伤害串的这个范围内中字符 1 的个数。
  3. 会修改伤害串中的数值,修改的方法是把 [l, r][l,~r] 中所有原来的字符 0 变成 1,将 1 变成 0

AKN 想知道一些时刻的伤害,请你帮助他求出这个伤害。

输入格式

输入的第一行有两个用空格隔开的整数,分别表示伤害串的长度 nn,和操作的个数 mm

输入第二行是一个长度为 nn 的字符串 SS,代表伤害串。

33 到第 (m+2)(m + 2) 行,每行有三个用空格隔开的整数 op,l,rop, l, r。代表第 ii 次操作的方式和区间,规则是:

  • op=0op = 0,则表示将伤害串的 [l, r][l,~r] 区间内的 0 变成 11 变成 0
  • op=1op = 1,则表示询问伤害串的 [l, r][l,~r] 区间内有多少个字符 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

提示

样例输入输出 11 解释

原伤害串为 1011101001

对于第一次操作,改变 [2, 4][2,~4] 的字符,伤害串变为 1100101001

对于第二次操作,查询 [1, 5][1,~5]1 的个数,共有 33 个。

对于第三次操作,改变 [3, 7][3,~7] 的字符,伤害串变为 1111010001

对于第四次操作,查询 [1, 10][1,~10]1 的个数,共有 66 个。

对于第五次操作,改变 [1, 4][1,~4] 的字符,伤害串变为 0000010001

对于第六次操作,查询 [2, 6][2,~6]1 的个数,共有 11 个。

数据范围与约定

对于 10%10\% 的数据,保证 n,m10n, m \leq 10

另有 30%30\% 的数据,保证 n,m2×103n, m \leq 2 \times 10^3

对于 100%100\% 的数据,保证 2n,m2×1052 \leq n, m \leq 2 \times 10^50op10 \leq op \leq 11lrn1 \leq l \leq r \leq nSS 中只含字符 0 和字符 1