「LOJ517」计算几何瞎暴力

Description

有一个长度为 nn 的数组 AA。下标从 11 开始标号。有 mm 个操作需要处理,操作有如下四种:

  1. 在数组 AA 的末尾添加一个数 xx

  2. 输出 i=lrAi\sum_{i=l}^{r}A_i

  3. 将数组 AA 中的每个数 AiA_i 都改为 AixA_i\oplus x。(\oplus 表示异或操作)。

  4. 将数组 AA 从小到大排序。

Input

第一行一个数 nn 表示 AA 的初始大小。
接下来一行 nn 个非负整数 AiA_i,表示 AA 的中的每个元素。
接下来一行一个数 表示询问的数量。
接下来 mm 行,每行表示一个操作:

  • 1 x: 表示第一种操作,在末尾插入数 xx
  • 2 l r:表示第二种操作,询问 i=lrAi\sum_{i=l}^{r}A_i。保证有 1lrn1\le l\le r\le n',其中 nn' 为操作时刻序列的长度。
  • 3 x:表示第三种操作,给每个数 \oplusxx
  • 4:表示第四种操作,将数组 AA 排序。

Output

对于每个第二种操作,输出答案。

Sample Input

1
2
3
4
5
6
7
8
5
5 2 6 2 0
5
2 1 5
1 2
3 7
2 2 6
4

Sample Output

1
2
15
23

HINT

1n,m105,0x,Ai1091\le n,\,m\le 10^5, 0\le x,A_i\le 10^9

Solution

调试的时候都直接一遍for输出各个儿子信息就行了,方便。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void setIO() {
freopen("lt.in","r",stdin);
freopen("lt.out","w",stdout);
}
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) x = -x, putchar('-');if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210000*4*3;
int a[N];
int n, pm, m;
const int H = 31;
struct Aft {
int s[N][32], xtag;
void ins(int x) {
x ^= xtag;
a[++m] = x;
for(int i = H; ~i; --i)
s[m][i] = s[m - 1][i] + ((x >> i) & 1);
}
ll query(int x) {
x += pm;
ll res = 0;
for(int i = H; ~i; --i)
if(xtag & (1 << i)) res += ((x - pm) - (s[x][i] - s[pm][i])) * (1ll << i);
else res += (s[x][i] - s[pm][i])* (1ll << i);
return res;
}
}aft;
struct Bef {
int ch[N][2], siz[N], tot, s[N][32][2], xtag;
void ins(int x) {
int p = 0;
for(int i = H; ~i; --i) {
int nxt = ((x >> i) & 1);
if(!ch[p][nxt]) ch[p][nxt] = ++tot;
p = ch[p][nxt];
++siz[p];
for(int j = H; ~j; --j)
++s[p][j][(x >> j) & 1];
}
}
ll query(int x) {
int p = 0, nxt;
ll res = 0;
if(!x) return 0;
for(int i = H; ~i; --i) {
int nxt = 0;
if(xtag & (1 << i)) nxt = 1;
if(ch[p][nxt] && siz[ch[p][nxt]] > x) p = ch[p][nxt]/*, printf("L")*/;
else {
for(int j = H; ~j; --j) {
int q = (aft.xtag >> j) & 1;
res += (s[ch[p][nxt]][j][q ^ 1] * (1ll << j));
}
x -= siz[ch[p][nxt]];
p = ch[p][nxt ^ 1];
if(!x) break;
}
}
if(!x) return res;
for(int j = H; ~j; --j) {
int q = (aft.xtag >> j) & 1;
res += ((s[p][j][q ^ 1] > 0 ? x : 0)* (1ll << j));
}
return res;
}
int size() {
return siz[ch[0][0]] + siz[ch[0][1]];
}
}bef;
ll query(int x) {
if(bef.size() >= x) return bef.query(x);
return aft.query(x - bef.size()) + bef.query(bef.size());
}
void clear() {
while(pm < m) {
bef.ins(a[++pm]);
}
bef.xtag = aft.xtag;
}
int main() {
n = read();
for(int i = 1; i <= n; ++i)
aft.ins(read());
int Q = read();
while(Q--) {
int op = read();
if(op == 1) aft.ins(read());
if(op == 2) {
int l = read(), r = read();
writeln(query(r) - query(l - 1));
}
if(op == 3) aft.xtag ^= read();
if(op == 4) clear();
}
return 0;
}