洛谷P2574 XOR的艺术

P2574 XOR的艺术

思路

通过题目数据量2*10 ^ 5 的数据可以想到线段树是可行的，可以开足够得结点来构建一颗线段树。
题目给的01串，每个“0”或“1”作为线段树的底部结点。通过线段树区间求和，可以轻松应对回答操作。
对于xor操作，将lazy标记下放时，不再是加加减减而是^1就OK了

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
#define mid ((l+r)/2)
using namespace std;
void read(int &x){
    x=0; char c=getchar(); int f=1;
    for(;!isdigit(c);c=getchar()) if (c=='-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; x*=f;
}
int n,m;
int tree[800010],lazy[800010];
void pushdown(int root,int wid){
	if (lazy[root]){
		lazy[root*2]^=1;    
        lazy[root*2+1]^=1;
        tree[root*2]=(wid-(wid>>1))-tree[root*2];        
        tree[root*2+1]=(wid>>1)-tree[root*2+1];    
        lazy[root]=0;
	}
}
void build(int root,int l,int r){
	if (l==r){ int c; scanf("%1d",&c); tree[root]=c; return;}
	build(root*2,l,mid); build(root*2+1,mid+1,r); 
	tree[root]=tree[root*2]+tree[root*2+1];
}
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);
	if (L<=mid) update(root*2,l,mid,L,R);
	if (R>mid) update(root*2+1,mid+1,r,L,R);
	tree[root]=tree[root*2]+tree[root*2+1];
}
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);
	int ans=0; 
	if (L<=mid) ans+=query(root*2,l,mid,L,R);
	if (R>mid) ans+=query(root*2+1,mid+1,r,L,R);
	return ans;
}
int main(){
	read(n),read(m);
	build(1,1,n);
	REP(i,1,m){
		int x,y,z; read(x),read(y),read(z);
		if (x==0) update(1,1,n,y,z);
			else cout<<query(1,1,n,y,z)<<endl;
	}
} 

The END