题目描述
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]的伤害
输出格式：
对于每次询问伤害，输出一个数值伤害，每次询问输出一行
输入输出样例
说明
样例解释：
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<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<string> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define N 200005 using namespace std; string a; int n,m,p,l,r; int num[N],tree[N<<2],lazy[N<<2]; void push(int root) { tree[root]=tree[root<<1]+tree[root<<1|1]; } void pushdown(int root,int len) { if(lazy[root]) { lazy[root<<1]^=1; //标志以当节点为根的子树要取反 lazy[root<<1|1]^=1; tree[root<<1]=(len-(len>>1))-tree[root<<1]; //异或，将原先状态全部翻转 tree[root<<1|1]=(len>>1)-tree[root<<1|1]; //该区间一共(r-l+1)>>1 个元素，减去自己即为异或后状态 lazy[root]=0; } } void build(int root,int l,int r) { if(l==r) //找到叶子节点 { scanf("%1d",&tree[root]); //%1d，只输入一个数字 return; } int mid=(l+r)>>1; build(lson); //建左子树 build(rson); //建右子树 push(root); } int query(int root,int l,int r,int L,int R) { if(L<=l&&r<=R) return tree[root]; //查询区间包含当前区间，直接返回当前区间的值 pushdown(root,r-l+1); //将lazy数组下放，更新子树节点 int mid=(l+r)>>1; int sum=0; if(L<=mid) sum+=query(lson,L,R); //查询左子树 if(mid<R) sum+=query(rson,L,R); //查询右子树 return sum; } void update(int root,int l,int r,int L,int R) { if(L<=l&&r<=R) { lazy[root]^=1; //表示以当前节点为根的子树要取反 tree[root]=r-l+1-tree[root]; //将当前子树中的值全部异或，总数减去当前数即为异或后的值 return; } pushdown(root,r-l+1); //更新子树 int mid=(l+r)>>1; if(L<=mid) update(lson,L,R); //更新左子树 if(mid<R) update(rson,L,R); //更新右子树 push(root); } int main() { scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&p,&l,&r); if(p==0) { update(1,1,n,l,r); } else { printf("%d ",query(1,1,n,l,r)); } } return 0; }