CF-242E.XOR on Segment（异或线段树）

传送门

解题思路

开21棵线段树，把数字拆成二进制存，然后对每一位进行操作。
注意+-*/和&^|等不能混用，都各自是闭环，两者毫无规律可言！
所以就开21棵线段树。
AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<vector>
11 #include<iomanip>
12 #include<ctime>
13 #include<stack>
14 using namespace std;
15 const int maxn=100005;
16 int n,m,d[21][maxn*4],lazy[21][maxn*4];
17 inline pushup(int node,int x){
18     d[node][x]=d[node][x*2]+d[node][x*2+1];
19 }
20 inline pushdown(int node,int id,int l,int mid,int r){
21     d[node][id*2]=(mid-l+1)-d[node][id*2];
22     d[node][id*2+1]=(r-mid)-d[node][id*2+1];
23     lazy[node][id*2]^=1;
24     lazy[node][id*2+1]^=1;
25     lazy[node][id]=0;
26 }
27 void add(int node,int id,int l,int r,int x){
28     if(l==r){
29         d[node][id]=1;
30         return;
31     }
32     int mid=(l+r)/2;
33     if(x<=mid) add(node,id*2,l,mid,x);
34     else add(node,id*2+1,mid+1,r,x);
35     pushup(node,id);
36 }
37 void reverse(int node,int id,int l,int r,int x,int y){
38     if(l>=x&&r<=y){
39         d[node][id]=(r-l+1)-d[node][id];
40         lazy[node][id]^=1;
41         return;
42     }
43     int mid=(l+r)/2;
44     if(lazy[node][id]) pushdown(node,id,l,mid,r);
45     if(x<=mid) reverse(node,id*2,l,mid,x,y);
46     if(y>mid) reverse(node,id*2+1,mid+1,r,x,y);
47     pushup(node,id);
48 }
49 int query(int node,int id,int l,int r,int x,int y){
50     if(l>=x&&r<=y) return d[node][id];
51     int mid=(l+r)/2,res=0;
52     if(lazy[node][id]) pushdown(node,id,l,mid,r);
53     if(x<=mid) res+=query(node,id*2,l,mid,x,y);
54     if(y>mid) res+=query(node,id*2+1,mid+1,r,x,y);
55     return res;
56 }
57 int main()
58 {
59     cin>>n;
60     for(int i=1;i<=n;i++){
61         int x,cnt=0;
62         scanf("%d",&x);    
63         while(x>0){
64             cnt++;
65             if(x&1){
66                 add(cnt,1,1,n,i);
67             }
68             x>>=1;
69         }
70     }
71     cin>>m;
72     for(int i=1;i<=m;i++){
73         int t;
74         scanf("%d",&t);
75         if(t==1){
76             int l,r;
77             scanf("%d%d",&l,&r);
78             long long res=1,ans=0;
79             for(int i=1;i<=20;i++){
80                 ans+=res*query(i,1,1,n,l,r);
81                 res*=2;
82             }
83             printf("%lld
",ans);
84         }else{
85             int l,r,x,cnt=0;
86             scanf("%d%d%d",&l,&r,&x);
87             while(x>0){
88                 cnt++;
89                 if(x&1){
90                     reverse(cnt,1,1,n,l,r);
91                 }
92                 x>>=1;
93             }
94         }
95     }
96     return 0;
97 }