洛谷 2574 XOR的艺术

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define N 200010
 6 #define rg register
 7 #define ls (u<<1)
 8 #define rs (u<<1|1)
 9 #define mid ((a[u].l+a[u].r)>>1)
10 #define len(x) (a[x].r-a[x].l+1)
11 using namespace std;
12 int n,m;
13 struct tree{
14     int l,r,sum; bool mark;
15 }a[N<<2];
16 inline int read(){
17     int k=0,f=1; char c=getchar();
18     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
19     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
20     return k*f;
21 }
22 void build(int u,int l,int r){
23     a[u].l=l; a[u].r=r;
24     if(l<r) 
25         build(ls,l,mid),build(rs,mid+1,r),a[u].sum=a[ls].sum+a[rs].sum;
26     else{
27         char c=getchar();
28         while(c!=‘0‘&&c!=‘1‘) c=getchar();
29         a[u].sum=c-‘0‘;
30     }
31 }
32 inline void pushdown(int u){
33     if(!a[u].mark) return; else a[u].mark^=1;
34     a[ls].mark^=1; a[ls].sum=len(ls)-a[ls].sum;
35     a[rs].mark^=1; a[rs].sum=len(rs)-a[rs].sum;
36 }
37 void update(int u,int r,int l){
38     if(l<=a[u].l&&a[u].r<=r){
39         a[u].sum=len(u)-a[u].sum;
40         a[u].mark^=1; 
41         return; 
42     }
43     pushdown(u);
44     if(l<=mid) update(ls,r,l);
45     if(r>mid) update(rs,r,l);
46     a[u].sum=a[ls].sum+a[rs].sum;
47 }
48 int query(int u,int r,int l){
49     if(l<=a[u].l&&a[u].r<=r) return a[u].sum;
50     pushdown(u); int ret=0;
51     if(l<=mid) ret+=query(ls,r,l);
52     if(r>mid) ret+=query(rs,r,l);
53     return ret;
54 }
55 int main(){
56     n=read(); m=read(); build(1,1,n);
57     while(m--){
58         if(read()==1) printf("%d\n",query(1,read(),read()));
59         else update(1,read(),read());
60     }
61     return 0;
62 }