洛谷 3870 [TJOI2009]开关

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define rg register
 6 #define N 200010
 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,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) build(ls,l,mid),build(rs,mid+1,r);
25 }
26 inline void pushdown(int u){
27     a[u].mark^=1;
28     a[ls].mark^=1; a[ls].sum=len(ls)-a[ls].sum;
29     a[rs].mark^=1; a[rs].sum=len(rs)-a[rs].sum;
30 }
31 void update(int u,int r,int l){
32     if(l<=a[u].l&&a[u].r<=r){
33         a[u].mark^=1;
34         a[u].sum=len(u)-a[u].sum;
35         return;
36     }
37     if(a[u].mark) pushdown(u);
38     if(l<=mid) update(ls,r,l);
39     if(r>mid) update(rs,r,l);
40     a[u].sum=a[ls].sum+a[rs].sum;
41 }
42 int query(int u,int r,int l){
43     if(l<=a[u].l&&a[u].r<=r) return a[u].sum;
44     if(a[u].mark) pushdown(u);
45     int ret=0;
46     if(l<=mid) ret+=query(ls,r,l);
47     if(r>mid) ret+=query(rs,r,l);
48     return ret;
49 }
50 int main(){
51     n=read(); m=read(); build(1,1,n);
52     while(m--){
53         int opt=read();
54         if(opt) printf("%d\n",query(1,read(),read()));
55         else update(1,read(),read());
56     }
57     return 0;
58 }