题目大意：
给定一个数列$a$，有以下几种询问：
1. 给定$x$，在序列末尾插入$x$。
2. 给定$l,r$，输出$\sum\limits_{i=l}^r a_i$。
3. 给定$x$，将数列中的所有数异或$x$。
4. 将当前数列从小到大排序。
解题思路：
考虑某一时刻数列的状态，一定是前面一段有序，后面一段无序。
首先考虑第三个操作，显然用一个变量记一下全局异或的值$X$就可以了。对于第一个操作，先把$x$异或上$X$再插入。
计算贡献的话，可以按位考虑，记录一下这一位有多少个即可。
如果没有排序操作，直接记一下每一位的前缀和即可。
考虑排序操作，前面有序的我们不去动它，后面无序的，直接把它插在正确的位置即可。显然一个数只会被插入一次。用01Trie或线段树维护一下区间各个位的出现次数即可做到区间查询（可以用前缀相减来搞）。
然而操作3会改变已经排完序的数的大小关系。我们考虑一下性质。
考虑最高位，如果它异或上了1，则这个序列的后一部分（最高位为1的那些数）会整体变到前面来。而每个部分内部的相对顺序不变。然后对每一部分，再对次高位考虑。依次类推。
对应到数据结构内部，我们发现，如果某一位异或上了1，相当于这一层的节点的左右儿子交换了一下。
我们不需要真的交换，只需要在询问的时候判断一下往哪边走即可。
这样就非常简单了，代码也很好写。
时间复杂度$O(n\log^2 A)$。
C++ Code：
#include<iostream>
#include<cstring>
const int N=2e5+5;
typedef long long LL;
int n,p,a[N],pre[N][31],A,m,cnt=1,ch[N<<4][2],wg[N<<4][31],sz[N<<4];
int STD;
inline void insert(const int&X){
int u=1;
for(int i=30;~i;--i){
++sz[u];
for(int j=0;j<31;++j)
wg[u][j]+=X>>j&1;
const int sn=X>>i&1;
if(!ch[u][sn])ch[u][sn]=++cnt;
u=ch[u][sn];
}
++sz[u];
for(int j=0;j<31;++j)
wg[u][j]+=X>>j&1;
}
LL query(int k){
LL ret=0;
int val=0;
int u=1;
for(int i=30;~i;--i){
const int _0=STD>>i&1;
if(sz[ch[u][_0]]>=k)u=ch[u][_0],val|=_0<<i;else{
int x=sz[ch[u][_0]];
k-=x;
for(int j=0;j<31;++j){
int cnt=wg[ch[u][_0]][j];
if(A>>j&1)cnt=x-cnt;
ret+=(LL)cnt<<j;
}
u=ch[u][!_0];
val|=!_0<<i;
}
}
val^=A;
return ret+(LL)val*k;
}
inline LL calc(int l,int r){
const int len=r-l+1;
LL ret=0;
for(int i=0;i<31;++i){
int cnt=pre[r][i]-pre[l-1][i];
if(A>>i&1)cnt=len-cnt;
ret+=(LL)cnt<<i;
}
return ret;
}
inline LL solve(int l,int r){return query(r)-query(l-1);}
int main(){
std::ios::sync_with_stdio(0),std::cin.tie(0),std::cout.tie(0);
std::cin>>n;p=1;
for(int i=1;i<=n;++i){
std::cin>>a[i];
for(int j=0;j<31;++j)
pre[i][j]=pre[i-1][j]+(a[i]>>j&1);
}
std::cin>>m;
while(m--){
int op;
std::cin>>op;
switch(op){
case 1:{
int x;
std::cin>>x;
x^=A;
a[++n]=x;
for(int i=0;i<31;++i)
pre[n][i]=pre[n-1][i]+(a[n]>>i&1);
break;
}
case 2:{
int l,r;
std::cin>>l>>r;
LL ans;
if(r<p)ans=solve(l,r);else
if(l>=p)ans=calc(l,r);else
ans=solve(l,p-1)+calc(p,r);
std::cout<<ans<<‘\n‘;
break;
}
case 3:{
int x;
std::cin>>x;
A^=x;
break;
}
case 4:{
for(int i=p;i<=n;++i)
insert(a[i]);
STD=A;
p=n+1;
memset(pre[n],0,sizeof*pre);
break;
}
}
}
return 0;
}
原文：https://www.cnblogs.com/Mrsrz/p/10755999.html