真的是萌新,真的是蒟蒻。
洛谷IDE和本地不一样。
#include <cstdio>
#include <cstdlib>
inline int max(const int x, const int y) {return x > y ? x : y;}
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Node {
int ch[2], r, v, cnt, s;
} t[200005];
int tot = 1, p, root = 1;
inline void maintain(const int O) {t[O].s = t[t[O].ch[0]].s + t[t[O].ch[1]].s + t[O].cnt;}
inline void rotate(int& O, const int d) {
int k(t[O].ch[d ^ 1]);
t[O].ch[d ^ 1] = t[k].ch[d], t[k].ch[d] = O;
maintain(O), maintain(k);
O = k;
}
void insert(int& O, const int x) {//option 1
++ t[O].s;
if (t[O].v == x) {++ t[O].cnt; return;}
int d(t[O].v < x);
if (t[O].ch[d]) {
insert(t[O].ch[d], x);
if (t[t[O].ch[d]].r > t[O].r) rotate(O, d ^ 1);
}
else {
t[O].ch[d] = ++ tot, t[tot].s = t[tot].cnt = 1, t[tot].v = x, t[tot].r = rand();
if (t[t[O].ch[d]].r > t[O].r) rotate(O, d ^ 1);
}
}
void remove(int& O, const int x) {//option 2
-- t[O].s;
if (t[O].v == x) {
-- t[O].cnt;
if (t[O].cnt) return;
if (!t[O].ch[0]) O = t[O].ch[1];
else if (!t[O].ch[1]) O = t[O].ch[0];
else {
int d(t[t[O].ch[0]].r < t[t[O].ch[1]].r);
rotate(O, d), remove(t[O].ch[d], x);
}
} else remove(t[O].ch[t[O].v < x], x);
}
int rank(int O, const int x) {//option 3
if (O == 0) return 0;
if (x < t[O].v) return rank(t[O].ch[0], x);
else return t[t[O].ch[0]].s + 1 + rank(t[O].ch[1], x);
}
int rank2(int O, const int x) {//option 4
if (x <= t[t[O].ch[0]].s) return rank2(t[O].ch[0], x);
if (x <= t[t[O].ch[0]].s + t[O].cnt) return t[O].v;
return rank2(t[O].ch[1], x - t[t[O].ch[0]].s - t[O].cnt);
}
bool find(int O, const int x) {
if (O == 0) return 0;
if (t[O].v == x) return 1;
return find(t[O].ch[t[O].v < x], x);
}
void Pre(int O, const int x) {// option 5
if (O == 0) return;
if (t[O].v < x) {
p = t[O].v;
Pre(t[O].ch[1], x);
}
else Pre(t[O].ch[0], x);
}
void Nxt(int O, const int x) {// option 6
if (O == 0) return;
if (t[O].v > x) {
p = t[O].v;
Nxt(t[O].ch[0], x);
}
else Nxt(t[O].ch[1], x);
}
int main() {
int n;
bool mark(0);
scanf("%d", &n);
while (n --) {
int opt, x;
scanf("%d%d", &opt, &x);
if (opt == 1) {
if (mark) insert(root, x);
else t[1].v = x, t[1].s = t[1].cnt = 1, t[1].r = rand();
mark = true;
}
else if (!mark) continue;
else if (opt == 2) {if (find(root, x)) remove(root, x);}
else if (opt == 3) printf("%d\n", rank(root, x));
else if (opt == 4) printf("%d\n", rank2(root, x));
else if (opt == 5) printf("%d\n", (Pre(root, x), p));
else if (opt == 6) printf("%d\n", (Nxt(root, x), p));
}
}