题目描述
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
思路：
线段树，只需要把Lazy标记部分改一下。
代码：
#include<cstdio>
using namespace std;
const int N=; int n,m,Sum[N<<],Lazy[N<<];
//char str[N]; void read(int &now)
{
now=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')now=now*+c-'',c=getchar();
} void PushUp(int rt)
{
Sum[rt]=Sum[rt<<]+Sum[rt<<|];
}
void PushDown(int rt,int m)
{
if(Lazy[rt])
{
Lazy[rt<<]^=;
Lazy[rt<<|]^=;
Sum[rt<<]=(m-(m>>))-Sum[rt<<];//异或(取反)，将原先状态全部翻转
Sum[rt<<|]=(m>>)-Sum[rt<<|];//该区间一共(r-l+1)>>1 个元素，减去自己即为异或后状态
Lazy[rt]=;
}
}
void Build(int l,int r,int rt)
{
Lazy[rt]=;
if(l==r)
{
int a;
scanf("%1d",&a);
Sum[rt]= a?:;
//Sum[rt]= str[l]=='1'?1:0;
return;
}
int m=(l+r)>>;
Build(l,m,rt<<);
Build(m+,r,rt<<|);
PushUp(rt);
}
void ModifyXor(int l,int r,int rt,int L,int R)
{
if(L<=l && r<=R)
{
Lazy[rt]^=;
Sum[rt]=r-l+-Sum[rt];
return;
}
PushDown(rt,r-l+);
int m=(l+r)>>;
if(L<=m) ModifyXor(l,m,rt<<,L,R);
if(m<R) ModifyXor(m+,r,rt<<|,L,R);
PushUp(rt);
}
int QuerySum(int l,int r,int rt,int L,int R)
{
if(L<=l && r<=R) return Sum[rt];
PushDown(rt,r-l+);
int m=(l+r)>>,res=;
if(L<=m) res+=QuerySum(l,m,rt<<,L,R);
if(m<R) res+=QuerySum(m+,r,rt<<|,L,R);
return res;
} int main()
{
read(n);read(m);//scanf("%s",str+1);
Build(,n,);
for(int i=;i<=m;i++)
{
int p,l,r;
read(p);read(l);read(r);
if(p)
printf("%d\n",QuerySum(,n,,l,r));
else
ModifyXor(,n,,l,r);
}
return ;
}