附代码
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long ll;
#define $(i, a, n) for(int i = a; i <= n; ++i)
using namespace std;
inline ll read() {
ll ans = 0;
char ch = getchar(), last = ' ';
while (ch < '0' || ch > '9') last = ch, ch = getchar();
while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
if (last == '-') return -ans;
return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 5;
int n, cnt;
struct node{
int l, r;
int v, size, key;
}z[20000005];
int rt[N];
void update(int x) {
z[x].size = z[z[x].l].size + z[z[x].r].size + 1;
}
int merge(int x, int y) {
if(x == 0 || y == 0) return x | y;
if(z[x].key > z[y].key) {
int t = ++cnt;
z[t] = z[x];
z[t].r = merge(z[t].r, y);
update(t);
return t;
} else {
int t = ++cnt;
z[t] = z[y];
z[t].l = merge(x, z[t].l);
update(t);
return t;
}
}
pair<int, int> spilt(int x, int v) {
if(x == 0) return make_pair(0, 0);
int t = ++cnt;
z[t] = z[x];
if(z[t].v <= v) {
pair<int, int> p = spilt(z[t].r, v);
z[t].r = p.first;
update(t);
return make_pair(t, p.second);
} else {
pair<int, int> p = spilt(z[t].l, v);
z[t].l = p.second;
update(t);
return make_pair(p.first, t);
}
}
pair<int, int> spilt_size(int x, int k) {
if(k == 0) return make_pair(0, x);
if(k == z[x].size) return make_pair(x, 0);
int t = ++cnt;
z[t] = z[x];
if(z[z[t].l].size >= k) {
pair<int, int> p = spilt_size(z[t].l, k);
z[t].l = p.second;
update(t);
return make_pair(p.first, t);
} else {
pair<int, int> p = spilt_size(z[t].r, k - z[z[t].r].size - 1);
z[t].r = p.first;
update(t);
return make_pair(t, p.second);
}
}
int newnode(int v) {
z[++cnt].key = rand();
z[cnt].l = z[cnt].r = 0;
z[cnt].v = v;
z[cnt].size = 1;
return cnt;
}
void insert(int &root, int v) {
pair<int, int> p = spilt(root, v);
root = merge(merge(p.first, newnode(v)), p.second);
}
void del(int &root, int v) {
pair<int, int> p = spilt(root, v - 1);
int p1 = p.first;
p = spilt_size(p.second, 1);
if(z[p.first].v != v) return;
root = merge(p1, p.second);
}
int kth(int x, int k) {
if(z[z[x].l].size >= k) {
return kth(z[x].l, k);
} else {
if(z[z[x].l].size + 1 == k) return z[x].v;
return kth(z[x].r, k - z[z[x].l].size - 1);
}
}
int rnk(int &root, int v) {
pair<int, int> p = spilt(root, v - 1);
int ans = z[p.first].size + 1;
root = merge(p.first, p.second);
return ans;
}
int pre(int &root, int v) {
pair<int, int> p = spilt(root, v - 1);
if(p.first == 0) {
root = merge(p.first, p.second);
return -2147483647;
}
int ans = kth(p.first, z[p.first].size);
root = merge(p.first, p.second);
return ans;
}
int suf(int &root, int v) {
pair<int, int> p = spilt(root, v);
if(p.second == 0) {
root = merge(p.first, p.second);
return 2147483647;
}
int ans = kth(p.second, 1);
root = merge(p.first, p.second);
return ans;
}
int main() {
//freopen("testdata.in", "r", stdin);
//freopen("ans.out", "w", stdout);
n = read();
int v, op, x;
for(int i = 1; i <= n; ++i) {
v = read(), op =read(), x = read();
rt[i] = rt[v];
if(op == 1) insert(rt[i], x);
else if(op == 2) del(rt[i], x);
else if(op == 3) printf("%d\n", rnk(rt[i], x));
else if(op == 4) printf("%d\n", kth(rt[i], x));
else if(op == 5) printf("%d\n", pre(rt[i], x));
else printf("%d\n", suf(rt[i], x));
}
return 0;
}
```
by Stream月 @ 2019-12-08 16:16:50