题解：
比较水吧
显然是平衡树的操作
然后就是写写写
用对拍来查错相比之下直接样例查还是比较容易的
刚开始没有优化常数没开O2就变成暴力分了smg 开了O2就a了
代码：
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define ll long long const int N=3e5; int a[N],rt,x1,x2; char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T>void read(T &x) { rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; } struct sgt{ int v[N][21],data[N],lazy[N],ls[N],rs[N],count2[N],fa[N]; bool rev[N]; IL void updata(rint x) { count2[x]=count2[ls[x]]+count2[rs[x]]+1; rint *a=v[x],*b=v[ls[x]],*c=v[rs[x]],d=data[x]; rep(i,0,20) a[i]=((d>>i)&1)+b[i]+c[i]; // rep(i,0,20) v[x][i]=((data[x]>>i)&1)+v[ls[x]][i]+v[rs[x]][i]; } IL void down(rint x) { if (rev[x]) { rev[ls[x]]^=1; rev[rs[x]]^=1; swap(ls[x],rs[x]); rev[x]=0; } if (lazy[x]) { if (ls[x]) { lazy[ls[x]]^=lazy[x]; data[ls[x]]^=lazy[x]; dep(i,20,0) if ((lazy[x]>>i)&1) v[ls[x]][i]=count2[ls[x]]-v[ls[x]][i]; } if (rs[x]) { lazy[rs[x]]^=lazy[x]; data[rs[x]]^=lazy[x]; dep(i,20,0) if ((lazy[x]>>i)&1) v[rs[x]][i]=count2[rs[x]]-v[rs[x]][i]; } lazy[x]=0; } } void rotate(rint x,rint y) { rint f1=fa[x]; if (y==1) { rs[f1]=ls[x]; if (ls[x]) fa[ls[x]]=f1; } else { ls[f1]=rs[x]; if (rs[x]) fa[rs[x]]=f1; } fa[x]=fa[f1]; if (fa[f1]) if (ls[fa[f1]]==f1) ls[fa[f1]]=x; else rs[fa[f1]]=x; fa[f1]=x; if (y==1) ls[x]=f1; else rs[x]=f1; updata(f1); updata(x); } void dfs(int x) { if (fa[x]) dfs(fa[x]); down(x); } void splay(rint x,rint y) { dfs(x); rint f1=fa[x]; while (f1!=y) { if (fa[f1]==y) if (ls[f1]==x) rotate(x,2); else rotate(x,1); else if (ls[fa[f1]]==f1) if (ls[f1]==x) rotate(f1,2),rotate(x,2); else rotate(x,1),rotate(x,2); else if (rs[f1]==x) rotate(f1,1),rotate(x,1); else rotate(x,2),rotate(x,1); f1=fa[x]; } if (!y) rt=x; } IL int search(rint x) { rint y=rt; while (y) { down(y); if (count2[ls[y]]+1==x) return(y); if (count2[ls[y]]>=x) y=ls[y]; else x-=count2[ls[y]]+1,y=rs[y]; } } IL void split(rint x,rint y) { x1=search(x); x2=search(y); splay(x2,0); splay(x1,x2); down(x2); down(x1); x1=rs[x1]; } }S; int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); int n,m; read(n); read(m); rep(i,1,n) read(a[i]); rep(i,1,n+1) { S.rs[i]=i+1,S.count2[i]=1,S.fa[i+1]=i,S.data[i]=a[i-1]; } S.splay(n+2,0); rep(i,1,m) { int kk,x,y,z; read(kk); read(x); read(y); if (kk==1) { S.split(x,y+2); S.rev[x1]^=1; S.splay(x1,0); } if (kk==2) { read(z); S.split(x,y+2); S.lazy[x1]^=z; S.data[x1]^=z; rep(i,0,20) if ((z>>i)&1) S.v[x1][i]=S.count2[x1]-S.v[x1][i]; S.splay(x1,0); } if (kk==3) { S.split(x,y+2); ll ans=0; dep(i,20,0) ans+=1ll*(1<<i)*S.v[x1][i]; cout<<ans<<endl; } } return 0; }