https://codeforces.com/problemset/problem/242/E
区间异或+区间和
题意：初始序列，两个操作，一：问区间和，二：区间每个数异或X；
题解：对每个结点建20棵树，维护每一个二进制位，维护每个区间的每一位有多少个1即可
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; struct node{ int w[20];//二进制 20 位 int lazy; }tree[maxn*4]; int a[maxn]; void push(int p){ for(int i=0;i<20;i++){ tree[p].w[i]=tree[p<<1].w[i]+tree[p<<1|1].w[i]; } } void get(int l,int r,int p,int val){ for(int i=0;i<20;i++){ if(val&(1<<i)){//判断两位置是否都是1 tree[p].w[i]=(r-l+1)-tree[p].w[i];//这N个数的第I位有多少个1 }//即1的位置取反 } } void pushdown(int l,int r,int p){ int mid=(l+r)/2; if(tree[p].lazy){ tree[p<<1].lazy^=tree[p].lazy; tree[p<<1|1].lazy^=tree[p].lazy; get(l,mid,p<<1,tree[p].lazy); get(mid+1,r,p<<1|1,tree[p].lazy); tree[p].lazy=0; } } void build(int l,int r,int p){ if(l==r){ for(int i=0;i<20;i++) if(a[l]&(1<<i))//当前位是1 tree[p].w[i]=1; else tree[p].w[i]=0; return; } int mid=(l+r)/2; build(l,mid,p<<1); build(mid+1,r,p<<1|1); push(p); } void update(int l,int r,int L,int R,int val,int p){ if(L<=l&&r<=R){ get(l,r,p,val); tree[p].lazy^=val; return ; } pushdown(l,r,p); int mid=(l+r)/2; if(L<=mid) update(l,mid,L,R,val,p<<1); if(R>mid) update(mid+1,r,L,R,val,p<<1|1); push(p); } ll query(int l,int r,int L,int R,int p){ if(L<=l&&r<=R){//区间和 ll tmp=1; ll res=0; for(int i=0;i<20;i++){ res+=tmp*tree[p].w[i];//该区间所有这1位有多少个1 tmp=tmp*2; } return res; } pushdown(l,r,p); int mid=(l+r)/2; ll ans=0; if(L<=mid) ans+=query(l,mid,L,R,p<<1); if(R>mid) ans+=query(mid+1,r,L,R,p<<1|1); return ans; } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } build(1,n,1); int q; scanf("%d",&q); while(q--){ int op;scanf("%d",&op); if(op==1){ int x,y; scanf("%d %d",&x,&y); ll ans=query(1,n,x,y,1); printf("%lld\n",ans); }else{ int x,y,val; scanf("%d %d %d",&x,&y,&val); update(1,n,x,y,val,1); } } return 0; }
