「K-th Number」第K小数

形式化题目

给定长度为 $n$ 的静态序列 $A$ 。对 $m$ 个询问 $(l, r, k)$ ，分别回答 $A[l..r]$ 中第 $k$ 小的值（重复的值按出现次数计）。 $n \leqslant 10^5$ ， $m \leqslant 10^4$ ， $|A_i| \leqslant 10^9$ 。

正解

思路

朴素做法：对每个询问，把 $A[l..r]$ 复制出来排序，取第 $k$ 个。单次询问 $O(n \log n)$ ，总共 $O(mn \log n) \approx 10^4 \times 10^5$ 次比较级的工作，无法承受。

第一个观察：把"区间"变成"前缀之差"。 数组是静态的， $A[l..r]$ 中每个值的出现次数，恰好等于"前 $r$ 个数中该值的出现次数"减去"前 $l-1$ 个数中该值的出现次数"。所以若我们能对每个前缀维护一个"按值统计次数"的权值线段树，则一次询问就是两棵线段树的对应节点做减法。问题在于： $n$ 棵完整的权值线段树要 $O(n^2)$ 空间。

第二个观察：相邻前缀只差一个数——可持久化。 前缀 $1..i$ 的线段树和前缀 $1..i-1$ 的线段树相比，只有从根到"值 $A_i$ 所在叶子"这一条链上的计数变了，其余部分完全相同。于是第 $i$ 棵树不必新建，只需从第 $i-1$ 棵树复用所有旧节点、沿这条链新建 $O(\log n)$ 个新节点即可。这就是可持久化线段树（主席树）： $n$ 次插入共用 $O(n \log n)$ 个节点。

查询：两棵树同步下降。 设 $u = root[l-1]$ ， $v = root[r]$ 。区间内落在值域左半区的个数是 $cnt[lc_v] - cnt[lc_u]$ ：若 $k$ 不超过它，第 $k$ 小在左半区，两棵树同时走左儿子；否则把 $k$ 减去左半个数，同时走右儿子。走到底时所在的叶子就是答案的离散化下标。

用样例 1 5 2 6 3 7 4 看查询 [2,5]（即 5 2 6 3，求第 3 小）：排序后为 2 3 5 6，第 3 小是 5。查询时先比较"左半区（较小的那些值）里有几个数"，再决定向左还是向右，每层只看一次计数差：

text

1
2
3
4
5值域（离散化后 7 个值: 1 2 3 4 5 6 7）
层级1  [1..7)  左半 {1,2,3} 有 2 个 (2,3)  → k=3 > 2，去右半，k←3-2=1
层级2  [4..7)  左半 {4,5}   有 1 个 (5)   → k=1 ≤ 1，去左半
层级3  [4..6)  左半 {4}     有 0 个      → 去右半，k 不变
层级4  [5..6)  只剩值 5                  → 答案 5

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 区间第 k 小：可持久化权值线段树，版本区间相减。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll MAXNODE = 3000000;

struct Node {
    int lc;  // 左儿子编号
    int rc;  // 右儿子编号
    int cnt; // 子树内数的个数
};

Node node[MAXNODE];
ll tot = 0;

std::vector<ll> vals;
std::vector<int> roots; // roots[i] = 插入前 i 个数后的树根

// 在 prev 版本上把离散化下标 pos 的计数 +1，返回新版本节点编号
int insert(int prev, ll lo, ll hi, ll pos) {
    tot++;
    int root = (int)tot;
    node[root] = node[prev];
    node[root].cnt++;
    int cur = root, old = prev;
    while (hi - lo > 1) {
        ll mid = (lo + hi) / 2;
        if (pos < mid) {
            tot++;
            int nd = (int)tot;
            node[nd] = node[node[old].lc];
            node[nd].cnt++;
            node[cur].lc = nd;
            cur = nd;
            old = node[old].lc;
            hi = mid;
        } else {
            tot++;
            int nd = (int)tot;
            node[nd] = node[node[old].rc];
            node[nd].cnt++;
            node[cur].rc = nd;
            cur = nd;
            old = node[old].rc;
            lo = mid;
        }
    }
    return root;
}

// 在版本区间 (u, v] 上求第 k 小的离散化下标
ll kth(int u, int v, ll k, ll lo, ll hi) {
    while (hi - lo > 1) {
        ll mid = (lo + hi) / 2;
        ll left_cnt = node[node[v].lc].cnt - node[node[u].lc].cnt; // 值落在左半区的个数
        if (k <= left_cnt) {
            u = node[u].lc;
            v = node[v].lc;
            hi = mid;
        } else {
            k -= left_cnt;
            u = node[u].rc;
            v = node[v].rc;
            lo = mid;
        }
    }
    return lo;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    std::vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    vals = a;
    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
    ll kinds = (ll)vals.size();

    roots.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) {
        ll pos = std::lower_bound(vals.begin(), vals.end(), a[i - 1]) - vals.begin();
        roots[i] = insert(roots[i - 1], 0, kinds, pos);
    }

    for (ll q = 0; q < m; q++) {
        ll l, r, k;
        scanf("%lld %lld %lld", &l, &r, &k); // 区间 [l,r] 的第 k 小 = 前缀 r 减前缀 l-1
        printf("%lld\n", vals[kth(roots[l - 1], roots[r], k, 0, kinds)]);
    }
    return 0;
}

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

# 主席树用三个平行数组存全部节点：下标即节点编号，0 号是"空节点"哨兵
lc: list[int] = [0]   # 左儿子编号
rc: list[int] = [0]   # 右儿子编号
cnt: list[int] = [0]  # 子树内数的个数
roots: list[int] = [0]  # roots[i] = 插入前 i 个数后的树根


def insert(prev: int, lo: int, hi: int, pos: int) -> int:
    """在 prev 版本上把离散化下标 pos 的计数 +1，返回新版本节点编号。"""
    node = len(cnt)
    lc.append(lc[prev])
    rc.append(rc[prev])
    cnt.append(cnt[prev] + 1)
    if hi - lo > 1:
        mid = (lo + hi) // 2
        if pos < mid:
            lc[node] = insert(lc[prev], lo, mid, pos)
        else:
            rc[node] = insert(rc[prev], mid, hi, pos)
    return node


def kth(u: int, v: int, k: int, lo: int, hi: int) -> int:
    """在值域 [lo,hi) 上，求版本区间 (u,v]（第 v 个前缀减第 u 个前缀）的第 k 小的离散化下标。"""
    while hi - lo > 1:
        mid = (lo + hi) // 2
        left_cnt = cnt[lc[v]] - cnt[lc[u]]  # 值落在左半区的个数
        if k <= left_cnt:
            u, v, hi = lc[u], lc[v], mid
        else:
            k -= left_cnt
            u, v, lo = rc[u], rc[v], mid
    return lo


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    a = [next(data) for _ in range(n)]

    # 离散化：值域压到 [0, len(vals))
    vals = sorted(set(a))
    rk = {v: i for i, v in enumerate(vals)}

    # 每个前缀建一个版本，共 n 次插入、每次 O(log n) 个新节点
    for x in a:
        roots.append(insert(roots[-1], 0, len(vals), rk[x]))

    out: list[str] = []
    for _ in range(m):
        l, r, k = next(data), next(data), next(data)
        # 区间 [l,r] 的第 k 小 = 前缀 r 减前缀 l-1 后的第 k 小
        out.append(str(vals[kth(roots[l - 1], roots[r], k, 0, len(vals))]))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

预处理： $n$ 次插入，每次新建一条 $O(\log n)$ 的链，时间与空间都是 $O(n \log n)$ 。
每次询问：两棵树同步下降一层只做一次减法， $O(\log n)$ 。
总计 $O((n + m)\log n)$ ，与数据范围匹配： $10^5 \times 17 + 10^4 \times 17$ 远小于朴素做法。

总结

静态区间第 $k$ 小的经典模型：前缀可减性 + 可持久化权值线段树。
两个关键转化：用"前缀之差"消去区间维度，用"路径复制"消去版本维度，两者共同把 $O(n^2)$ 的空间压到 $O(n \log n)$ 。
实现要点：先离散化把值域压到 $O(n)$ ；主席树用平行数组存节点，下标即节点编号， $0$ 号节点兼任"空节点"哨兵，省去所有空指针判断。

图示解析

主席树版本共享

下图展示样例中依次插入 1, 5, 2 后，第 3 棵树（root[3]）如何与第 2 棵树共享大部分节点，只新建一条从根到值 2 叶子的链：

graph TD
    subgraph root2["root[2]：已插入 1, 5"]
        A2["[1..7) cnt=2"] --> B2["[1..4) cnt=1"]
        A2 --> C2["[4..7) cnt=1"]
        B2 --> D2["[1..2) cnt=1"]
        B2 --> E2["[2..4) cnt=0"]
        C2 --> F2["[4..6) cnt=1"]
        C2 --> G2["[6..7) cnt=0"]
    end
    subgraph root3["root[3]：再插入 2（新建 3 个节点，加粗）"]
        A3["[1..7) cnt=3"] --> B3["[1..4) cnt=2"]
        A3 --> C3["[4..7) cnt=1（旧）"]
        B3 --> D3["[1..2) cnt=1（旧）"]
        B3 --> E3["[2..4) cnt=1"]
        C3 -.复用 root2 的节点.-> C2
        D3 -.复用.-> D2
    end

观察重点：插入值 2 只影响从根到叶子 [2..4) 的路径，所以 root[3] 只有 3 个新节点（根、[1..4)、[2..4)）；右子树 [4..7) 和左深处的 [1..2) 都直接指回 root[2] 的旧节点。 $n$ 个版本合起来只建 $O(n \log n)$ 个节点，而不是 $n$ 棵完整的树。