类似权值线段树分裂合并维护区间排序的套路，可以考虑用某个维护权值的数据结构来维护有序的那一段。
而此题涉及异或，考虑 01 Trie。
如果没有 \(4\) 操作，用个什么数据结构维护下每一位上 \(1\) 的个数就行了，并整体维护一个异或标记。
如果没有 \(1\) 操作，异或可能会影响大小关系，但是考虑到异或某一位相当于在 Trie 上把某一层所有左右儿子交换，于是打个标记即可。
综合起来，就是每次排序时就把上一次排序到这一次排序新加的数插入即可。
（我才不会说一开始我排序的时候没更新每次有序段的边界，插入的时候还没异或呢）
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
using namespace std;
const int N = 2e5;
const int LG = 30;
int n,m,ls,a[N + 5],sum[N + 5][LG + 5];
int Xor,Tag;
int ch[(N << 4) + 10][2],sz[(N << 4) + 10],cnt[(N << 4) + 10][LG + 5],rt;
void insert(int x,int &cur)
{
static int tot = 0;
int p = cur ? cur : (cur = ++tot);
++sz[p];
for(register int i = 0;i < LG;++i)
cnt[p][i] += (x >> i) & 1;
for(register int i = LG - 1;~i;--i)
{
!ch[p][(x >> i) & 1] && (ch[p][(x >> i) & 1] = ++tot);
p = ch[p][(x >> i) & 1],++sz[p];
for(register int j = 0;j < LG;++j)
cnt[p][j] += (x >> j) & 1;
}
}
long long query(int k,int p)
{
if(!k)
return 0;
int v = 0;
long long ret = 0;
for(register int i = LG - 1;~i;--i)
if(k <= sz[ch[p][(Tag >> i) & 1]])
p = ch[p][(Tag >> i) & 1],v |= Tag & (1 << i);
else
{
k -= sz[ch[p][(Tag >> i) & 1]];
for(register int j = 0;j < LG;++j)
ret += (long long)((Xor & (1 << j)) ? (sz[ch[p][(Tag >> i) & 1]] - cnt[ch[p][(Tag >> i) & 1]][j]) : cnt[ch[p][(Tag >> i) & 1]][j]) << j;
p = ch[p][((Tag >> i) & 1) ^ 1],v |= (Tag & (1 << i)) ^ (1 << i);
}
return ret + (long long)(v ^ Xor) * k;
}
long long query1(int l,int r)
{
return query(r,rt) - query(l - 1,rt);
}
long long query2(int l,int r)
{
long long ret = 0;
for(register int i = 0;i < LG;++i)
ret += (long long)((Xor & (1 << i)) ? (r - l + 1 - sum[r][i] + sum[l - 1][i]) : (sum[r][i] - sum[l - 1][i])) << i;
return ret;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
{
scanf("%d",a + i);
for(register int j = 0;j < LG;++j)
sum[i][j] = sum[i - 1][j] + ((a[i] >> j) & 1);
}
scanf("%d",&m);
for(int op,x,y;m;--m)
{
scanf("%d",&op);
if(op == 1)
{
scanf("%d",&x),a[++n] = x ^ Xor;
for(register int i = 0;i < LG;++i)
sum[n][i] = sum[n - 1][i] + ((a[n] >> i) & 1);
}
else if(op == 2)
{
scanf("%d%d",&x,&y);
printf("%lld\n",x > ls ? query2(x,y) : (y <= ls ? query1(x,y) : query1(x,ls) + query2(ls + 1,y)));
}
else if(op == 3)
scanf("%d",&x),Xor ^= x;
else
{
for(register int i = ls + 1;i <= n;++i)
insert(a[i],rt);
ls = n,Tag = Xor,memset(sum[n],0,sizeof sum[n]);
}
}
}