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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129 | #include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
typedef unsigned int u32;
typedef unsigned long long u64;
mt19937_64 MT(114514);
namespace Treap{
const int SIZ = 1e6 + 1e5 + 3;
int F[SIZ], C[SIZ], S[SIZ], W[SIZ], X[SIZ][2], sz;
u64 H[SIZ];
bool is_root(int x){ return F[x] == 0;}
bool is_rson(int x){ return X[F[x]][1] == x;}
int newnode(int w){
W[++ sz] = w, C[sz] = S[sz] = 1; H[sz] = MT();
return sz;
}
void pushup(int x){
S[x] = C[x] + S[X[x][0]] + S[X[x][1]];
}
void rotate(int &root, int x){
int y = F[x], z = F[y];
bool f = is_rson(x);
bool g = is_rson(y);
int &t = X[x][!f];
if(z){ X[z][g] = x; } else root = x;
if(t){ F[t] = y; }
X[y][f] = t, t = y;
F[y] = x, pushup(y);
F[x] = z, pushup(x);
}
void insert(int &root, int w){
if(root == 0) {root = newnode(w); return;}
int x = root, o = x;
for(;x;o = x, x = X[x][w > W[x]]){
++ S[x]; if(w == W[x]){ ++ C[x], o = x; break;}
}
if(W[o] != w){
if(w < W[o]) X[o][0] = newnode(w), F[sz] = o, o = sz;
else X[o][1] = newnode(w), F[sz] = o, o = sz;
}
while(!is_root(o) && H[o] < H[F[o]])
rotate(root, o);
}
void erase(int &root, int w){
int x = root, o = x;
for(;x;o = x, x = X[x][w > W[x]]){
-- S[x]; if(w == W[x]){ -- C[x], o = x; break;}
}
if(C[o] == 0){
while(X[o][0] || X[o][1]){
u64 wl = X[o][0] ? H[X[o][0]] : ULLONG_MAX;
u64 wr = X[o][1] ? H[X[o][1]] : ULLONG_MAX;
if(wl < wr){
int p = X[o][0]; rotate(root, p);
} else {
int p = X[o][1]; rotate(root, p);
}
}
if(is_root(o)){
root = 0;
} else {
X[F[o]][is_rson(o)] = 0;
}
}
}
int find_rank(int &root, int w){
int x = root, o = x, a = 0;
for(;x;){
if(w < W[x])
o = x, x = X[x][0];
else {
a += S[X[x][0]];
if(w == W[x]){
o = x; break;
}
a += C[x];
o = x, x = X[x][1];
}
}
return a + 1;
}
int find_kth(int &root, int w){
int x = root, o = x, a = 0;
for(;x;){
if(w <= S[X[x][0]])
o = x, x = X[x][0];
else {
w -= S[X[x][0]];
if(w <= C[x]){
o = x; break;
}
w -= C[x];
o = x, x = X[x][1];
}
}
return W[x];
}
int find_pre(int &root, int w){
return find_kth(root, find_rank(root, w) - 1);
}
int find_suc(int &root, int w){
return find_kth(root, find_rank(root, w + 1));
}
}
int qread();
int main(){
using namespace Treap;
int n = qread(), m = qread(), root = 0;
up(1, n, i){
int a = qread(); insert(root, a);
}
int last_ans = 0, ans = 0;
up(1, m, i){
int op = qread(), x = qread() ^ last_ans;
switch(op){
case 1 : insert(root, x); break;
case 2 : erase (root, x); break;
case 3 : ans ^= (last_ans = find_rank(root, x)); break;
case 4 : ans ^= (last_ans = find_kth (root, x)); break;
case 5 : ans ^= (last_ans = find_pre (root, x)); break;
case 6 : ans ^= (last_ans = find_suc (root, x)); break;
}
}
printf("%d\n", ans);
return 0;
}
|