题目链接：

---

 

线段树要求支持区间求和，区间内每一个数字异或上一个值。

 

　　既然是异或，考虑每一个节点维护一个长度为$21*2$的数组${c[x][w][0,1]}$，表示这个节点的子树所包含的线段的点中，这个$2$进制位置上的为$0$和为$1$的分别有多少个。那么一次异或操作其实就是交换了这个位置上的0，1的个数。线段树普通做就可以了。

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 400100 10 #define llg long long 11 #define SIZE 22 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,c[maxn][SIZE][2],xorv[maxn],cnt,T; 14 llg ans; 15 16 inline int getint() 17 { 18 int w=0,q=0; char c=getchar(); 19 while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 20 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w; 21 } 22 23 void update(llg o) 24 { 25 llg lc=o<<1,rc=o<<1|1; 26 for (llg i=0;i
            
             >1; 72 build(lc,l,mid); build(rc,mid+1,r); 73 update(o); 74 } 75 76 void X(llg o,llg l,llg r,llg L,llg R,llg v) 77 { 78 pushdown(o,l,r); 79 if (l>=L && r<=R) 80 { 81 xorv[o]^=v; 82 xor_(o,v); 83 return ; 84 } 85 llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1; 86 if (mid>=L) X(lc,l,mid,L,R,v); 87 if (R>mid) X(rc,mid+1,r,L,R,v); 88 update(o); 89 } 90 91 void sum(llg o,llg l,llg r,llg L,llg R) 92 { 93 pushdown(o,l,r); 94 if (l>=L && r<=R) 95 { 96 for (llg i=0;i
             
              >1;100 if (mid>=L) sum(lc,l,mid,L,R);101 if (R>mid) sum(rc,mid+1,r,L,R);102 update(o);103 }104 105 int main()106 {107 yyj("seg");108 cin>>n;109 build(1,1,n);110 cin>>T;111 while (T--)112 {113 ans=0;114 llg x,y,z,type;115 type=getint();116 if (type==1)117 {118 x=getint(),y=getint(),ans=0;119 sum(1,1,n,x,y);120 printf("%lld\n",ans);121 }122 else123 {124 x=getint(),y=getint(),z=getint();125 X(1,1,n,x,y,z);126 }127 }128 return 0;129 }