XOR on Segment(线段树+XOR)

按每一个二进制位拆成20棵线段树即可.
所以对于每颗线段树$i$,我们关心的都只有一位,即二进制第$i$位上是否有1.
线段树节点上维护一个cnt,表明这个线段内在该位上1的个数.
lazy标记维护0或1,向下传递时1表明会改变子线段的cnt,即cnt=len-cnt.
传送门

#include<bits/stdc++.h> using namespace std; #define ll long long
#define MAXN 100002 #define fore(n) for(int i=1;i<=n;i++) ll n,m; int a[MAXN]; struct tree{ int l; int r; ll cnt; ll lazy; }tree[20][4*MAXN]; int d; void build(int rt,int l,int r) { tree[d][rt].l=l; tree[d][rt].r=r; if(l==r) { tree[d][rt].lazy=0; tree[d][rt].cnt=0; return; } int mid=(l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); } void pushdown(int rt) { if(tree[d][rt].lazy==0)return; tree[d][rt<<1].lazy^=tree[d][rt].lazy; tree[d][rt<<1|1].lazy^=tree[d][rt].lazy; tree[d][rt<<1].cnt=(tree[d][rt<<1].r-tree[d][rt<<1].l+1)-tree[d][rt<<1].cnt; tree[d][rt<<1|1].cnt=(tree[d][rt<<1|1].r-tree[d][rt<<1|1].l+1)-tree[d][rt<<1|1].cnt; tree[d][rt].lazy=0; } void update(int rt,int l,int r) { if(l>r)return; if(tree[d][rt].l>=l&&tree[d][rt].r<=r) { int len=tree[d][rt].r-tree[d][rt].l+1; tree[d][rt].cnt=len-tree[d][rt].cnt; tree[d][rt].lazy^=1; return ; } int mid=(tree[d][rt].l+tree[d][rt].r)>>1; pushdown(rt); update(rt<<1,l,min(r,mid)); update(rt<<1|1,max(l,mid+1),r); tree[d][rt].cnt=tree[d][rt<<1].cnt+tree[d][rt<<1|1].cnt; } ll query(int rt,int l,int r) { if(l>r)return 0; if(tree[d][rt].l>=l&&tree[d][rt].r<=r) { return tree[d][rt].cnt*(1<<d); } int mid=(tree[d][rt].l+tree[d][rt].r)>>1; pushdown(rt); ll res=query(rt<<1,l,min(r,mid))+query(rt<<1|1,max(l,mid+1),r); return res; } int main() { //freopen("E://tt.txt","r",stdin); ios::sync_with_stdio(false); cin>>n; fore(20) { d=i-1; build(1, 1, n); } fore(n){ cin>>a[i]; for(int x=1,j=0;x<=a[i];x<<=1,j++) { if(a[i]&x){ d=j; update(1,i,i); } } } cin>>m; while(m--) { int cmd;cin>>cmd; int l,r,x; if(cmd==1) { cin>>l>>r; ll ans=0; fore(20){ d=i-1; ans+=query(1,l,r); } cout<<ans<<endl; } else { cin>>l>>r>>x; fore(20) { if(x&(1<<(i-1))){ d=i-1; update(1,l,r); } } } } } 

本文地址：https://blog.csdn.net/weixin_43353639/article/details/107715929