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 | #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int INF = 1e9;
const i64 INFL = 1e18;
namespace BLOCK{
const int SIZ = 1e6 + 1e5 + 3;
const int BSZ = 2000;
list <vector<int> > block;
void build(int n, const int A[]){
for(int l = 0, r = 0;r != n;){
l = r;
r = min(l + BSZ / 2, n);
vector <int> V0(A + l, A + r);
block.emplace_back(V0);
}
}
int get_kth(int k){
for(auto it = block.begin();it != block.end();++ it){
if(it -> size() < k)
k -= it -> size();
else return it -> at(k - 1);
}
return -1;
}
int get_rank(int w){
int ans = 0;
for(auto it = block.begin();it != block.end();++ it){
if(it -> back() < w)
ans += it -> size();
else {
ans += lower_bound(it -> begin(), it -> end(), w) - it -> begin();
break;
}
}
return ans + 1;
}
// 插入到第 k 个位置
void insert(int k, int w){
for(auto it = block.begin();it != block.end();++ it){
if(it -> size() < k)
k -= it -> size();
else{
it -> insert(it -> begin() + k - 1, w);
if(it -> size() > BSZ){
vector <int> V1(it -> begin(), it -> begin() + BSZ / 2);
vector <int> V2(it -> begin() + BSZ / 2, it -> end());
*it = V2;
block.insert(it, V1);
}
return;
}
}
}
// 删除第 k 个数
void erase(int k){
for(auto it = block.begin();it != block.end();++ it){
if(it -> size() < k)
k -= it -> size();
else{
it -> erase(it -> begin() + k - 1);
if(it -> empty())
block.erase(it);
return;
}
}
}
}
int qread();
const int MAXN = 1e5 + 3;
int A[MAXN];
// ===== TEST =====
int main(){
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1;i <= n;++ i)
cin >> A[i];
sort(A + 1, A + 1 + n);
A[n + 1] = INT_MAX;
BLOCK :: build(n + 1, A + 1);
int last = 0;
int ans = 0;
for(int i = 1;i <= m;++ i){
int op;
cin >> op;
if(op == 1){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_rank(x);
BLOCK :: insert(k, x);
} else
if(op == 2){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_rank(x);
BLOCK :: erase(k);
} else
if(op == 3){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_rank(x);
last = k, ans ^= last;
} else
if(op == 4){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_kth (x);
last = k, ans ^= last;
} else
if(op == 5){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_rank(x);
last = BLOCK :: get_kth (k - 1), ans ^= last;
} else
if(op == 6){
int x; cin >> x; x ^= last;
int k = BLOCK :: get_rank(x + 1);
last = BLOCK :: get_kth (k), ans ^= last;
}
}
cout << ans << endl;
return 0;
}
|