|
n u; if (t[u].val < x && !f) return u; u = t[u].ch[f]; //后继往左找，前驱往右找
while (t[u].ch[f ^ 1]) u = t[u].ch[f ^ 1]; return u; } inline int rank(int x) { int u = root; if (t[u].sum < x) return 0; while (1) { int v = t[u].ch[0]; if (x > t[v].sum + t[u].cnt) { //如果排名比左儿子的大小和当前节点的数量要大
x -= t[v].sum + t[u].cnt; //那么当前排名的数一定在右儿子上找
u = t[u].ch[1]; } else if (t[v].sum >= x) u = v; else return t[u].val; } } inline void Del(int x) { int last = nx(x, 0), nxt = nx(x, 1); splay(last, 0), splay(nxt, last); int del = t[nxt].ch[0]; if (t[del].cnt > 1) { t[del].cnt--; splay(del, 0); } else t[nxt].ch[0] = 0; } int main(int argc, char const *argv[]) { insert(2147483647), insert(-2147483647); read(n); while (n --) { int opt, k; read(opt); if (opt == 1) read(k), insert(k); else if (opt == 2) read(k), Del(k); else if (opt == 3) { read(k); find(k); printf("%d\n", t[t[root].ch[0]].sum); } else if (opt == 4) { read(k); printf("%d\n", rank(k + 1)); } else if (opt == 5) { read(k); printf("%d\n", t[nx(k, 0)].val); } else if (opt == 6) { read(k); printf("%d\n", t[nx(k, 1)].val); } } return 0; }
Splay模板
|