【题解】
线段树基础题。对于每个修改操作把相应区间的sum改为区间长度-sum即可。
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 } View Code
转载于:https://www.cnblogs.com/DriverLao/p/9397608.html
相关资源：数据结构—成绩单生成器