Template

Posted on Edited on

普通BST(Binary Search Tree)：一种二叉树，保证所有节点的值都比左儿子大（如有），且比右儿子小（如有）。这样，这种二叉树的前序遍历就一定是一个递增序列。

在随机情况下，这个数据结构的表现非常好，但是有心人总喜欢卡它，比如说这道题就过不去：

https://www.luogu.com.cn/problem/P3369

Show Code 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 100001, INF = 1e7 + 1;
int rt, son[N][2]/*两个儿子*/, 
        val[N]/*当前节点值*/, 
        cnt[N]/*当前节点个数*/, 
        sz[N]/*当前节点子树内个数*/, 
        tot/*总结点数*/;
inline int newnode(int x){ // 加新点
    val[++tot] = x;
    cnt[tot] = 1;
    sz[tot] = 1;
    return tot;
}
inline void pushup(int x){ // 更新节点信息
    sz[x] = sz[son[x][0]] + sz[son[x][1]] + cnt[x];
}
int Insert(int u, int x){ // 插入节点，值为x
    if (!u) return newnode(x);
    if (val[u] == x) return ++cnt[u], u; // 多个表达式用逗号连接，返回最后一个。
    if (val[u] < x) son[u][1] = Insert(son[u][1], x);
    else son[u][0] = Insert(son[u][0], x);
    return pushup(u), u;
}
void Delete(int u, int x){ // 删除值为x的节点
    if (val[u] == x) --cnt[u];
    else if (val[u] < x) Delete(son[u][1], x);
    else Delete(son[u][0], x);
    return pushup(u);
}
int Rank(int u, int x){ // 查询x是第几大的节点
    if (!u) return 1;
    if (val[u] < x) return sz[son[u][0]] + cnt[u] + Rank(son[u][1], x);
    else if (val[u] == x) return sz[son[u][0]] + 1;
    else return Rank(son[u][0], x);
}
int QueryK(int u, int k){ // 查询排名为k的数
    if (k <= sz[son[u][0]]) return QueryK(son[u][0], k);
    if (k <= sz[son[u][0]] + cnt[u]) return val[u];
    return QueryK(son[u][1], k - sz[son[u][0]] - cnt[u]);
}
signed main(){
    int n; scanf("%d", &n);
    while (n--){
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) rt = Insert(rt, x);
        else if (opt == 2) Delete(rt, x);
        else if (opt == 3) printf("%d\n", Rank(rt, x));
        else if (opt == 4) printf("%d\n", QueryK(rt, x));
        else if (opt == 5) printf("%d\n", QueryK(rt, Rank(rt, x) - 1));
        else if (opt == 6) printf("%d\n", QueryK(rt, Rank(rt, x + 1)));
    }
    return 0;
}