「模板」替罪羊树

上课学kdt,先打一个替罪羊。

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
130
131
132
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<vector>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
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) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 210000;
int n;
int rt;
int ch[N][2];
int s[N], c[N], tot, val[N], d[N];
double alpha = 0.7;
bool isb(int x) {
return s[ch[x][0]] > s[x] * alpha || s[ch[x][1]] > s[x] * alpha;
}
void up(int x) {
s[x] = s[ch[x][0]] + s[ch[x][1]] + c[x];
}
void dfs(int x, vector<int> &v) {
if(ch[x][0])dfs(ch[x][0], v);
if(!d[x]) v.pb(x);
if(ch[x][1]) dfs(ch[x][1], v);
}
int build(vector<int> &v, int l, int r) {
if(l > r) return 0;
int mid = (l + r) >> 1;
int x = v[mid];
ch[x][0] = ch[x][1] = 0;
up(x);
if(l < mid) ch[x][0] = build(v, l, mid-1);
if(r > mid) ch[x][1] = build(v, mid + 1, r);
up(x);
return x;
}
void rebuild(int &jd) {
vector<int>v;
dfs(jd, v);
jd = build(v, 0, v.size()-1);
}
void insert(int &jd, int v) {
if(!jd) {
jd = ++tot;
s[jd] = c[jd] = 1;
val[jd] = v;
return ;
} else {
++s[jd];
if(v == val[jd]) {
++c[jd];
d[jd] = 0;
return;
}
if(v < val[jd]) insert(ch[jd][0], v);
else insert(ch[jd][1], v);
if(isb(jd))
rebuild(jd);
}
}
const int inf = 1e9 + 7;
pii getrak(int v) {
int now = rt, ans = 0;
while(now) {
if(val[now] == v) return mk(ans + s[ch[now][0]] + 1, c[now]); //不是ans+1
if(v <= val[now]) now = ch[now][0];
else ans += s[ch[now][0]] + c[now], now = ch[now][1];
}
return mk(ans, -inf);
} //返回a≤v 的位置
int getval(int v) {
int now = rt;
while(1) {
if(v > s[ch[now][0]] && v <= s[ch[now][0]] + c[now]) return val[now];
if(v <= s[ch[now][0]]) now = ch[now][0];
else v -= s[ch[now][0]] + c[now], now = ch[now][1];
}
return 0;
}
int getpre(int v) { //不能像treap和slplay一样
/*
可能出现
1-> (2,3)
然后1已经被删除,查询3的前驱就跪了
*/
pii t = getrak(v);
return getval(t.fi-(t.nd != -inf));
}
int getnxt(int v) {
pii t = getrak(v);
return getval(t.fi + (t.nd == -inf ? 1 : t.nd)); //getrak(v) + c[v]
//前驱和后继是最容易错的

}
void Remove(int jd, int v) {
--s[jd];
if(val[jd] == v) {
if(c[jd] == 1) d[jd] = 1;
--c[jd];
return;
}
if(v < val[jd]) Remove(ch[jd][0], v);
else Remove(ch[jd][1], v);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i) {
int op = read(), x = read();
if(op == 1) insert(rt,x);
if(op == 2) Remove(rt, x);
if(op == 3)
writeln(getrak(x).fi);
if(op == 4)
writeln(getval(x));
if(op == 5)
writeln(getpre(x));
if(op == 6)
writeln(getnxt(x));
}
return 0;
}