Luogu P3369 【模板】普通平衡树
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
using namespace std;
int rt = 0, tot = 0;
int par[MAX_N];
int ch[MAX_N][2];
int w[MAX_N];
int cnt[MAX_N];
int siz[MAX_N];
void pushup(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}
int get(int x) {
return ch[par[x]][1] == x;
}
void rot(int x) {
int y = par[x], z = par[y], c = get(x), d = get(y);
ch[y][c] = ch[x][c ^ 1], par[ch[y][c]] = y;
ch[x][c ^ 1] = y, par[y] = x;
par[x] = z;
if (z) ch[z][d] = x;
pushup(y), pushup(x);
}
void splay(int x) {
for (int y; y = par[x]; rot(x)) {
if (par[y]) {
rot(get(x) == get(y) ? y : x);
}
}
rt = x;
}
void ins(int v) {
if (!rt) {
w[++tot] = v, cnt[tot]++, rt = tot;
pushup(rt);
return;
}
int cur = rt, p = 0;
while (true) {
if (w[cur] == v) {
cnt[cur]++;
pushup(cur), pushup(p);
splay(cur);
return;
}
p = cur, cur = ch[cur][v > w[cur]];
if (!cur) {
w[++tot] = v, cnt[tot]++, par[tot] = p, ch[p][v > w[p]] = tot;
pushup(tot), pushup(p);
splay(tot);
return;
}
}
}
int rk(int v) {
int res = 0, cur = rt;
while (true) {
if (v < w[cur]) {
cur = ch[cur][0];
} else {
res += siz[ch[cur][0]];
if (w[cur] == v) {
splay(cur);
return res + 1;
}
res += cnt[cur];
cur = ch[cur][1];
}
}
}
int kth(int k) {
int cur = rt;
while (true) {
if (k <= siz[ch[cur][0]]) {
cur = ch[cur][0];
} else {
k -= siz[ch[cur][0]] + cnt[cur];
if (k <= 0) {
splay(cur);
return w[cur];
}
cur = ch[cur][1];
}
}
}
int pre() {
int cur = ch[rt][0];
while (ch[cur][1]) cur = ch[cur][1];
splay(cur);
return cur;
}
int suc() {
int cur = ch[rt][1];
while (ch[cur][0]) cur = ch[cur][0];
splay(cur);
return cur;
}
void del(int v) {
rk(v);
if (cnt[rt] > 1) {
cnt[rt]--;
pushup(rt);
return;
}
if (!ch[rt][0] && !ch[rt][1]) {
rt = 0;
return;
}
if (!ch[rt][0] || !ch[rt][1]) {
rt = ch[rt][0] + ch[rt][1];
par[rt] = 0;
return;
}
int cur = rt, x = pre();
ch[x][1] = ch[cur][1], par[ch[x][1]] = x;
pushup(x);
}
int main() {
ios::sync_with_stdio(false);
int n, op, x;
cin >> n;
while (n--) {
cin >> op >> x;
if (op == 1) {
ins(x);
} else if (op == 2) {
del(x);
} else if (op == 3) {
cout << rk(x) << endl;
} else if (op == 4) {
cout << kth(x) << endl;
} else if (op == 5) {
ins(x);
cout << w[pre()] << endl;
del(x);
} else {
ins(x);
cout << w[suc()] << endl;
del(x);
}
}
}