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
| inline int rand(){
static int seed = 233;
return seed = int(seed * 48271LL % 2147483647);
}
struct Treap{
int ch[maxn][2], key[maxn], size[maxn], rnd[maxn], cnt[maxn], sz, root;
Treap(){ root = sz = 0; }
void clear(){ root = sz = 0; }
void pushup(int rt){ size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + cnt[rt]; }
void rot(int& x, int k){
int v = ch[x][k ^ 1];
ch[x][k ^ 1] = ch[v][k];
ch[v][k] = x;
x = v;
pushup(ch[x][k]); pushup(x);
}
void insert(int& x, int val){
if (!x){
x = ++sz;
ch[x][0] = ch[x][1] = 0;
key[x] = val; rnd[x] = rand();
size[x] = cnt[x] = 1;
return;
}
if (key[x] == val){
cnt[x]++; pushup(x);
return;
}
int k = val > key[x];
insert(ch[x][k], val);
if (rnd[x] < rnd[ch[x][k]]) rot(x, k ^ 1);
pushup(x);
}
void del(int& x, int val){
if (!x) return;
if (key[x] == val){
if (cnt[x] > 1) {
cnt[x]--; pushup(x);
return;
}
if (ch[x][0] || ch[x][1]){
if (!ch[x][1] || rnd[ch[x][0]] > rnd[ch[x][1]]){
rot(x, 1); del(ch[x][1], val);
}
else {
rot(x, 0); del(ch[x][0], val);
}
pushup(x);
return;
}
x = 0;
return;
}
del(ch[x][val > key[x]], val);
pushup(x);
}
int find(int x, int val){
if (!x) return 0;
if (val == key[x]) return size[ch[x][0]] + 1;
else if (val < key[x]) return find(ch[x][0], val);
else return size[ch[x][0]] + cnt[x] + find(ch[x][1], val);
}
int findx(int x, int rank){
if (!x) return inf;
if (rank <= size[ch[x][0]]) return findx(ch[x][0], rank);
else if (rank <= size[ch[x][0]] + cnt[x]) return key[x];
else return findx(ch[x][1], rank - size[ch[x][0]] - cnt[x]);
}
int prev(int v){
int x = root, ans = 0;
while (x){
if (v > key[x]) ans = key[x], x = ch[x][1];
else x = ch[x][0];
}
return ans;
}
int succ(int v){
int x = root, ans = 0;
while (x){
if (v < key[x]) ans = key[x], x = ch[x][0];
else x = ch[x][1];
}
return ans;
}
}f;
|