【深基16.例7】普通二叉树（简化版）

题意

维护一个无重复整数集合，支持排名、第 k 小、前驱、后继和插入，共不超过 10^4 次操作。

思路

始终保持列表升序：

bisect_left(x)+1 是 x 的排名；
第 k 小直接访问 numbers[k-1]；
bisect_left(x)-1 是前驱位置；
bisect_right(x) 是后继位置；
insort 在正确位置插入。

查询都是 $O(\log q)$ ，列表中间插入需要移动后缀，是 $O(q)$ 。本题只有 10^4 次操作，标准库写法足够简洁可靠；更大范围才需要平衡树。

Python 知识

bisect_left/right 分别定位左、右插入边界。
insort 等价于先二分位置再 list.insert。
边界不存在时按题目输出固定哨兵值。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：维护和使用有序序列。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：多行操作与批量输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys
from bisect import bisect_left, bisect_right, insort


input = sys.stdin.buffer.readline
numbers = []
answers = []

for _ in range(int(input())):
    operation, value = map(int, input().split())
    if operation == 1:
        answers.append(str(bisect_left(numbers, value) + 1))
    elif operation == 2:
        answers.append(str(numbers[value - 1]))
    elif operation == 3:
        index = bisect_left(numbers, value)
        answers.append(str(numbers[index - 1] if index else -2147483647))
    elif operation == 4:
        index = bisect_right(numbers, value)
        answers.append(str(numbers[index] if index < len(numbers) else 2147483647))
    else:
        insort(numbers, value)

print("\n".join(answers))

cpp

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * P5076 【深基16.例7】普通二叉树（简化版）
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int INF = 2147483647;

// BST 结点：值、左/右孩子、出现次数、子树大小
struct Node {
    int val, l, r, cnt, sz;
} tree[MAXN];
int root, idx;

// 新建结点
int new_node(int val) {
    ++idx;
    tree[idx].val = val;
    tree[idx].l = tree[idx].r = 0;
    tree[idx].cnt = tree[idx].sz = 1;
    return idx;
}

// 插入，维护子树大小
void insert(int &u, int val) {
    if (u == 0) { u = new_node(val); return; }
    ++tree[u].sz;
    if (val == tree[u].val) { ++tree[u].cnt; return; }
    if (val < tree[u].val) insert(tree[u].l, val);
    else insert(tree[u].r, val);
}

// 查询 val 的排名（比 val 小的个数 + 1）
int get_rank(int u, int val) {
    if (u == 0) return 1;
    if (val == tree[u].val) return tree[tree[u].l].sz + 1;
    if (val < tree[u].val) return get_rank(tree[u].l, val);
    return tree[tree[u].l].sz + tree[u].cnt + get_rank(tree[u].r, val);
}

// 查询第 k 小的值
int kth(int u, int k) {
    if (u == 0) return 0;
    int lsz = tree[tree[u].l].sz;
    if (k <= lsz) return kth(tree[u].l, k);
    if (k <= lsz + tree[u].cnt) return tree[u].val;
    return kth(tree[u].r, k - lsz - tree[u].cnt);
}

// 前驱：小于 val 的最大值
int pre(int u, int val) {
    if (u == 0) return -INF;
    if (tree[u].val >= val) return pre(tree[u].l, val);
    return max(tree[u].val, pre(tree[u].r, val));
}

// 后继：大于 val 的最小值
int nxt(int u, int val) {
    if (u == 0) return INF;
    if (tree[u].val <= val) return nxt(tree[u].r, val);
    return min(tree[u].val, nxt(tree[u].l, val));
}

int main() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1) printf("%d\n", get_rank(root, x));
        else if (op == 2) printf("%d\n", kth(root, x));
        else if (op == 3) printf("%d\n", pre(root, x));
        else if (op == 4) printf("%d\n", nxt(root, x));
        else insert(root, x);
    }
    return 0;
}

复杂度

查询 $O(\log q)$ ，插入最坏 $O(q)$ ，总时间最坏 $O(q^2)$ ，空间 $O(q)$ 。

总结

题目规模决定实现：bisect 负责边界语义，列表负责第 k 小；在一万次操作下可用更短的标准库方案。

【深基16.例7】普通二叉树（简化版）

目录

题意

思路

Python 知识

代码

复杂度

总结