题目描述

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

1、 拥有一个伤害串为长度为n的01串。

2、 给定一个范围[l,r],伤害为伤害串的这个范围内中1的个数

3、 会被随机修改伤害串中的数值,修改的方法是把[l,r]中的所有数xor上1

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

输入输出格式

输入格式:

第一行两个数n,m,表示长度为n的01串,有m个时刻

第二行一个长度为n的01串,为初始伤害串

第三行开始m行,每行三个数p,l,r

若p为0,则表示当前时刻改变[l,r]的伤害串,改变规则如上

若p为1,则表示当前时刻AKN想知道[l,r]的伤害

输出格式:

对于每次询问伤害,输出一个数值伤害,每次询问输出一行

输入输出样例

输入样例#1:

10 6
1011101001
0 2 4
1 1 5
0 3 7
1 1 10
0 1 4
1 2 6

输出样例#1:

3
6
1

说明

样例解释:

1011101001

1100101001

询问[1,5]输出3

1111010001

询问[1,10]输出6

0000010001

询问[2,6]输出1

数据范围:

10%数据2≤n,m≤10

另有30%数据2≤n,m≤2000

100%数据2≤n,m≤2*10^5

By:worcher


把标记变成取反就行了,
修改值的话是将区间长度-区间大小

 



说点什么

avatar
  Subscribe  
提醒