我们要维护这四种操作：
-
在数组 A的末尾添加一个数 x。
-
输出 ∑ai（l to r）
-
将数组 A 中的每个数 A xor 一个数。
-
将数组 A 从小到大排序。
那么我们注意一件事，能很好的维护 XOR 操作的数据结构并不多：
1.路权并查集（什么鬼）
2.树状数组。
3.trie tree
4. 线性基
。。。
我们发现这道题 1,2,4显然不科学。
我们要处理的询问只有3，那么我们只要求前缀和即可。
我们考虑如何维护4操作：
我们发现我们很难在严格的O（log N^2）或更少的时间维护这个操作，我们考虑摊还分析。(就像cf 896E一样)
我们发现处理单个元素的时间复杂度应该在O(sqrt N)以内，但我并没有想到分块的做法，因为排序所带的log 很难去掉。
我们用 trie 来解决：
首先要保证每个元素应该进trie一次。我们认为每个元素进入trie后便是有序的。（XOR 操作的干扰下文将仔细的描述）
那么没有进入trie的元素我们用前缀和统计：
我们统计前缀元素在每一二进制位上出现几次，那么我们应该可以再O（log ）复杂度内维护前缀和。
void Int(int tot,int x){//统计前缀和，依次插入每个元素 for (int j=0;j<31;j++,x>>=1) sum[tot][j]=sum[tot-1][j]+(x&1); }
for (int i=30;~i;i--) //假设我们已经统计出在XOR last 之前我们在每一位上1的个数，那么我们可以这样统计答案 ans+=1ll*((last>>i)&1?x-anw[i]:anw[i])<<i;//X是前缀和的元素个数
那么我们就解决了1,2,3操作（如果没有4的话）
我们考虑4操作，之前讲了我们要让每个元素进trie一次，那么我们就很快的得出了在trie中的有序序列。
那么我们在XOR操作以后怎么知道原来的顺序呢？
我们统计在最后一次排序的时候，整个数组被哪个数 XOR 过了，统计顺序时XOR回去再做。
我们整理一下：
1操作： 我们得到一个数，XOR当前数组的懒标记，我们将其塞进前缀和数组里。
2操作： 我们把懒标记再XOR 当前要亦或的数。
3操作： 我们求前缀和:当 当前要求的末元素未进入trie时，我们用前缀和查询，如果在trie里，遍历trie上在 trie的懒标记下的最大值。
4操作：我们把当前所有未进入trie的数压入trie，并更新trie的懒标记。
#pragma GCC optimize("-O2") #include<bits/stdc++.h> #define getchar nc #define LL long long #define sight(c) (‘0‘<=c&&c<=‘9‘) #define deg printf #define dput puts #define dwln writeln #define dwl #define N 200007 #define db double #define eho(x) for(int i=head[x];i;i=net[i]) inline char nc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ static char c; for (c=getchar();!sight(c);c=getchar()); for (x=0;sight(c);c=getchar())x=x*10+c-48; } void write(LL x){if (x<10) {putchar(‘0‘+x); return;} write(x/10); putchar(‘0‘+x%10);} inline void writeln(LL x){ if (x<0) putchar(‘-‘),x*=-1; write(x); putchar(‘\n‘); } inline void writel(LL x){ if (x<0) putchar(‘-‘),x*=-1; write(x); putchar(‘ ‘); } using namespace std; struct Node{int son[2],ch[31],val;}T[N<<5|1]; int tot,Tot=1,last,lazy,n,sum[N][31],anw[31],to,x,a[N],root=1,m,op,l,r,tre_lazy; void Int(int tot,int x){ for (int j=0;j<31;j++,x>>=1) sum[tot][j]=sum[tot-1][j]+(x&1); } void ins(int x,int dep,int No){ T[No].val++; for (int j=0,t=x;t;j++,t>>=1) T[No].ch[j]+=t&1; if (dep==-1) return; int w=(x>>dep)&1; if (!T[No].son[w]) T[No].son[w]=++Tot; ins(x,dep-1,T[No].son[w]); } void find(int k,int dep,int No){ if (!k) return; if (dep==-1) { for (int i=30;~i;i--) anw[i]+=min(k,T[No].ch[i]); return; } if ((tre_lazy>>dep)&1) swap(T[No].son[0],T[No].son[1]); if (T[T[No].son[0]].val<=k) { for (int i=30;~i;i--) //anw[i]+=((last>>i)&1)?T[T[No].son[0]].val-T[T[No].son[0]].ch[i]:T[T[No].son[0]].ch[i]; anw[i]+=T[T[No].son[0]].ch[i]; find(k-T[T[No].son[0]].val,dep-1,T[No].son[1]); } else find(k,dep-1,T[No].son[0]); if ((tre_lazy>>dep)&1) swap(T[No].son[0],T[No].son[1]); } LL query(int x){ if (x==0) return 0; memset(anw,0,sizeof anw); if (x>=to) for (int i=30;~i;i--) anw[i]=sum[x][i]; else find(x,30,root); LL ans=0; for (int i=30;~i;i--) ans+=1ll*((last>>i)&1?x-anw[i]:anw[i])<<i; return ans; } signed main() { // freopen("d.in","r",stdin); // freopen("d.out","w",stdout); read(n); for(int i=1;i<=n;i++) {read(a[i]); Int(i,a[i]);} tot=n; read(m); while (m--) { read(op); switch (op) { case 1: read(x); a[++tot]=x^last;Int(tot,a[tot]); break; case 2: read(l); read(r); dwl(query(r)),dwl(r), dwl(query(l-1)),dwl(l-1),dwl(to),dwl(last),dwl(tre_lazy), writeln(query(r)-query(l-1)); break; case 3: read(lazy); last^=lazy; break; case 4: tre_lazy=last;while (to^tot) ins(a[++to],30,root); break; } } return 0; }