#P18284. Light Drinking and Low Singing
Light Drinking and Low Singing
Light Drinking and Low Singing
给定一个长度为 的二进制序列,你需要依次执行 次操作。操作有以下三种:
- 对于区间 ,将区间内部所有相邻的
01同时变为10。 - 对于区间 ,将区间内部所有相邻的
10同时变为01。 - 查询区间 中
1的数量。
一次操作中,所有匹配都根据操作前的序列确定;交换后新出现的匹配不会在本次操作中继续交换。只有两个位置都在区间内部的相邻数对才能交换。
输入格式
第一行包含两个整数 (,)。
第二行包含一个长度为 、仅由字符 0 和 1 组成的字符串,表示初始序列。
接下来 行,每行包含三个整数 (,),表示操作的类型及区间端点。
输出格式
对于每个第 3 类操作,输出一行一个整数,表示查询的答案。
若不存在第 3 类操作,则不需要输出。 时,第 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