题意：

一个01序列，初始全部元素为0，两种操作：l到r全部元素取反、询问l到r1的个数。序列长度≤100000，询问个数≤100000。

题解：

线段树维护区间和，区间修改就让区间和变为区间长度减原区间和。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 400010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 int sm[maxn],n,m,lr[maxn]; bool tg[maxn];16 void update(int x){sm[x]=sm[x<<1]+sm[x<<1|1];}17 void pushdown(int x){18     if(tg[x]){19         if(lr[x<<1])sm[x<<1]=lr[x<<1]-sm[x<<1],tg[x<<1]^=1;20         if(lr[x<<1|1])sm[x<<1|1]=lr[x<<1|1]-sm[x<<1|1],tg[x<<1|1]^=1;21         tg[x]^=1;22     }23 }24 void build(int x,int l,int r){25     lr[x]=r-l+1; if(l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r);26 }27 void modify(int x,int l,int r,int ql,int qr){28     pushdown(x); if(ql<=l&&r<=qr){tg[x]^=1; sm[x]=lr[x]-sm[x]; return;} int mid=(l+r)>>1;29     if(ql<=mid)modify(x<<1,l,mid,ql,qr); if(mid
         
          <<1|1,mid+1,r,ql,qr); update(x);30 }31 int query(int x,int l,int r,int ql,int qr){32     pushdown(x); if(ql<=l&&r<=qr)return sm[x]; int mid=(l+r)>>1,q=0;33     if(ql<=mid)q+=query(x<<1,l,mid,ql,qr); if(mid
          
           <<1|1,mid+1,r,ql,qr); return q;34 }35 int main(){36 n=read(); m=read(); build(1,1,n);37 inc(i,1,m){38 int opt=read(),l=read(),r=read(); if(!opt)modify(1,1,n,l,r);else printf("%d\n",query(1,1,n,l,r));39 }40 return 0;41 }
          
         
        
       
      
     

 

20160917