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
| namespace WBLT {
int ch[N][2], siz[N], val[N];
int pool[N], tot, poolc;
int Id () { return poolc ? pool[poolc--] : ++tot; }
int Recycle (int x) { pool[++poolc] = x; }
int Pushup (int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]];
val[x] = siz[ch[x][1]];
}
int New (int &x, int v) {
x = Id(); ch[x][0] = ch[x][1] = 0, siz[x] = 1, val[x] = v;
}
int Merge (int x, int y) {
int k = Id();
ch[k][0] = x, ch[k][1] = y;
Pushup(k); return k;
}
void Rotate (int x, int op) {
int temp = ch[x][op ^ 1];
ch[x][op ^ 1] = ch[x][op];
ch[x][op] = ch[ch[op ^ 1]][op];
ch[ch[x][op ^ 1]][op] = ch[ch[x][op ^ 1]][op ^ 1];
ch[ch[x][op ^ 1]][op ^ 1] = temp;
Pushup(ch[x][op ^ 1]);
}
const double alpha = 2.;
void Maintain (int x) {
if (siz[ch[x][0]] > siz[ch[x][1]] * alpha) Rotate (x, 0);
else
if (siz[ch[x][1]] > siz[ch[x][0]] * alpha) Rotate (x, 1);
if (siz[ch[x][0]] > siz[ch[x][1]] * alpha) Rotate (ch[x][0], 1), Rotate(x, 0);
else
if (siz[ch[x][1]] > siz[ch[x][0]] * alpha) Rotate (ch[x][1], 0), Rotate (x, 1);
}
void Insert (int &x, int v) {
if (!x) return New(x, v), void();
if (siz[x] == 1) return (x = v > val[x] ? Merge(val[x], v) : Merge(v, val[x])), void();
else Insert(ch[x][v > val[ch[x][0]]], v);
Pushup(x), Maintain(x);
}
void Delete (int &x, int v) {
if ( siz[x] == 1 ) return (Recycle(x), x = 0), void();
int to = v > val[ch[x][0]];
if ( siz[ch[x][to]] == 1 ) Recycle(x), Recycle(ch[x][to]), x = ch[x][to ^ 1];
else Delete (ch[x][to], v), Pushup(x), Maintain(x);
}
int Rank (int x, int v) {
if (siz[x] == 1) return 1;
if (v > val[ch[x][0]]) return siz[ch[x][0]] + Rank(ch[x][1], v);
return Rank(ch[x][0], v);
}
int Find (int x, int v) {
if (siz[x] == v) return val[x];
if (v > siz[ch[x][0]]) return Find(ch[x][1], v - siz[ch[x][0]]);
return Find(ch[x][0], v);
}
}
|
