#P18284. Light Drinking and Low Singing

Light Drinking and Low Singing

Light Drinking and Low Singing

给定一个长度为 nn 的二进制序列,你需要依次执行 qq 次操作。操作有以下三种:

  1. 对于区间 [l,r][l,r],将区间内部所有相邻的 01 同时变为 10。
  2. 对于区间 [l,r][l,r],将区间内部所有相邻的 10 同时变为 01。
  3. 查询区间 [l,r][l,r] 中 1 的数量。

一次操作中,所有匹配都根据操作前的序列确定;交换后新出现的匹配不会在本次操作中继续交换。只有两个位置都在区间内部的相邻数对才能交换。

输入格式

第一行包含两个整数 n,qn,q(1≤n≤2×1061\le n\le 2\times10^6,1≤q≤2500001\le q\le250000)。

第二行包含一个长度为 nn、仅由字符 0 和 1 组成的字符串,表示初始序列。

接下来 qq 行,每行包含三个整数 t,l,rt,l,r(1≤t≤31\le t\le3,1≤l≤r≤n1\le l\le r\le n),表示操作的类型及区间端点。

输出格式

对于每个第 3 类操作,输出一行一个整数,表示查询的答案。

若不存在第 3 类操作,则不需要输出。l=rl=r 时,第 1、2 类操作不会改变序列。

样例

10 10
0011101100
2 5 9
3 2 5
1 1 10
1 1 5
3 4 6
1 2 5
2 4 9
3 5 10
3 2 7
3 1 8
2
1
3
3
4