struct Query { int id, k; // 这个询问的编号, 这个询问的 k};int ans[N], a[N]; // ans[i] 表示编号为i的询问的答案，a 为原数列int val[N], cnt[N]; // 离散化后，记录对应的值及其计数（假设已经处理好）// 返回原数列中值域在 [l,r] 中的数的个数int check(int l, int r) { int res = 0; for (int i = l; i <= r; i++) { res += cnt[i]; } return res;}// 整体二分void solve(int l, int r, vector<Query> q) { int m = (l + r) / 2; if (l == r) { for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = val[l]; return; } vector<Query> q1, q2; int t = check(l, m); for (unsigned i = 0; i < q.size(); i++) { if (q[i].k <= t) q1.push_back(q[i]); else q[i].k -= t, q2.push_back(q[i]); } solve(l, m, q1), solve(m + 1, r, q2); return;}
查询区间第 k 小
题 3 在一个数列中多次查询区间第 k 小的数。
涉及到给定区间的查询，再按之前的方法进行二分就会导致 check 函数的时间复杂度爆炸。仍然考虑询问与值域中点 m 的关系：若询问区间内小于等于 m 的数有 t 个，询问的是区间内的 k 小数，则当 k≤t 时，答案应小于等于 m；否则，答案应大于 m。（注意边界问题）此处需记录一个区间小于等于指定数的数的数量，即单点加，求区间和，可用树状数组快速处理。为提高效率，只对数列中值在值域区间 [l,r] 的数进行统计，即，在进一步递归之前，不仅将询问划分，将当前处理的数按值域范围划为两半。
参考代码（关键部分）
实现
struct Num { int p, x;}; // 位于数列中第 p 项的数的值为 xstruct Query { int l, r, k, id;}; // 一个编号为 id, 询问 [l,r] 中第 k 小数的询问int ans[N];void add(int p, int x); // 树状数组, 在 p 位置加上 xint query(int p); // 树状数组, 求 [1,p] 的和void clear(); // 树状数组, 清空void solve(int l, int r, vector<Num> a, vector<Query> q)// a中为给定数列中值在值域区间 [l,r] 中的数{ int m = (l + r) / 2; if (l == r) { for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l; return; } vector<Num> a1, a2; vector<Query> q1, q2; for (unsigned i = 0; i < a.size(); i++) if (a[i].x <= m) a1.push_back(a[i]), add(a[i].p, 1); else a2.push_back(a[i]); for (unsigned i = 0; i < q.size(); i++) { int t = query(q[i].r) - query(q[i].l - 1); if (q[i].k <= t) q1.push_back(q[i]); else q[i].k -= t, q2.push_back(q[i]); } clear(); solve(l, m, a1, q1), solve(m + 1, r, a2, q2); return;}
#include <algorithm>#include <iostream>using namespace std;constexpr int N = 200020;int n, m;int ans[N];// BIT beginint t[N];int a[N];int sum(int p) { int ans = 0; while (p) { ans += t[p]; p -= p & (-p); } return ans;}void add(int p, int x) { while (p <= n) { t[p] += x; p += p & (-p); }}// BIT endint tot = 0;struct Query { int l, r, k, id, type; // set values to -1 when they are not used!} q[N * 2], q1[N * 2], q2[N * 2];void solve(int l, int r, int ql, int qr) { if (ql > qr) return; if (l == r) { for (int i = ql; i <= qr; i++) if (q[i].type == 2) ans[q[i].id] = l; return; } int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0; for (int i = ql; i <= qr; i++) { if (q[i].type == 1) { if (q[i].l <= mid) { add(q[i].id, 1); q1[++cnt1] = q[i]; } else q2[++cnt2] = q[i]; } else { int x = sum(q[i].r) - sum(q[i].l - 1); if (q[i].k <= x) q1[++cnt1] = q[i]; else { q[i].k -= x; q2[++cnt2] = q[i]; } } } // rollback changes for (int i = 1; i <= cnt1; i++) if (q1[i].type == 1) add(q1[i].id, -1); // move them to the main array for (int i = 1; i <= cnt1; i++) q[i + ql - 1] = q1[i]; for (int i = 1; i <= cnt2; i++) q[i + cnt1 + ql - 1] = q2[i]; solve(l, mid, ql, cnt1 + ql - 1); solve(mid + 1, r, cnt1 + ql, qr);}pair<int, int> b[N];int toRaw[N];int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; // read and discrete input data for (int i = 1; i <= n; i++) { int x; cin >> x; b[i].first = x; b[i].second = i; } sort(b + 1, b + n + 1); int cnt = 0; for (int i = 1; i <= n; i++) { if (b[i].first != b[i - 1].first) cnt++; a[b[i].second] = cnt; toRaw[cnt] = b[i].first; } for (int i = 1; i <= n; i++) { q[++tot] = {a[i], -1, -1, i, 1}; } for (int i = 1; i <= m; i++) { int l, r, k; cin >> l >> r >> k; q[++tot] = {l, r, k, i, 2}; } solve(0, cnt + 1, 1, tot); for (int i = 1; i <= m; i++) cout << toRaw[ans[i]] << '\n';}
树套树和整体二分实现带修区间第 k 小问题的复杂度都为 O(nlog2n)，但静态区间第 k 小问题可以使用可持久化线段树在 O(nlogn) 时间复杂度内解决，而几乎所有整体二分实现的静态区间第 k 小问题代码时间复杂度都是 O(nlog2n)，面对大数据范围时存在 TLE 的风险。（这里默认值域与序列长度同阶，值域与序列长不同阶的情况可以通过离散化转化为同阶情况）
优化
对于每一轮划分，如果当前数列中小于等于 mid 的数有 t 个，则将询问划分后实际是在右区间询问第 k−t 小数，因此对划分到右区间的询问做出了修改。如果答案的原始值域为 [L,R]，某次划分的答案值域为 [l,r]，那么对于参与此次划分的询问，[L,l) 中所有数值对它们的影响已经在之前被消除了。