学了一下，感觉不深刻。
说是整体二分，不如说是离线的归并排序。
考虑这个问题：Luogu P3834 【模板】可持久化线段树 2
\(m\) 次询问，每次询问给出 \((l,r,k)\)，问 \([l,r]\) 中第 \(k\) 小的值。
我们首先先简化一下：如果 \(m=1\)，怎么维护？
先二分出一个 \(x\)，建立树状数组维护 \(\le x\) 的个数，判断其是否小于 \(k\) 即可。
那加入 \(m\) 次询问怎么办呢？
可以离线下来，运用分治思想将同一范围内的答案统一处理。
具体的，我们定义结构体 \((x,y,k,id,opt)\)。对于询问，\(x,y,k\) 表示查询 \([x,y]\) 的第 \(k\) 小，此时的 \(opt=1\)，对于原数，\(x\) 表示原值。
定义操作函数 solve(l,r,L,R) 表示当前处理到 \([l,r]\)，值域为 \([L,R]\)，对于 \(L=R\)，显然，\(l\sim r\) 的答案就为 \(L\)（\(R\)）。
-
对于原数，如果 \(x\le mid\)，那么其在树状数组上的位置就加一。
-
对于询问，查询 \([x,y]\) 的个数相当于查询原数的值在 \([L,mid]\) 的个数，我们令为 \(p\)，如果 \(p\ge k\)，那么此时答案在 \([L,mid]\) 中，否则在 \([mid+1,R]\) 中，需要注意，此时的 \(q_i\) 的 \(k\) 要减去 \(p\)。
码风有点抽象，切勿锐评 /qd。
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 100;
int n, m, cnt, mn = 1e18, mx = -1e18, ans[N];
struct Node {
int x, y, k, id, opt;
} q[N], q1[N], q2[N];
struct Bit {
int f[N];
int lowbit(int x) { return x & -x; }
void add(int x, int k) { while (x <= n) { f[x] += k; x += lowbit(x); } }
int getsum(int x) { int sum = 0; while (x) { sum += f[x]; x -= lowbit(x); } return sum; }
} bit;
void solve(int l, int r, int L, int R) {
if (l > r) return ;
if (L == R) { for (int i = l; i <= r; i++) { if (q[i].opt) { ans[q[i].id] = L; } } return ; }
int mid = (L + R) >> 1, p1 = 0, p2 = 0;
for (int i = l; i <= r; i++) { if (!q[i].opt) { if (q[i].x <= mid) { bit.add(q[i].id, 1); q1[++p1] = q[i]; } else { q2[++p2] = q[i]; } } else { int num = bit.getsum(q[i].y) - bit.getsum(q[i].x - 1); if (num >= q[i].k) { q1[++p1] = q[i]; } else { q[i].k -= num; q2[++p2] = q[i]; } } }
for (int i = 1; i <= p1; i++) { if (!q1[i].opt) { bit.add(q1[i].id, -1); } }
for (int i = 1; i <= p1; i++) { q[i + l - 1] = q1[i]; }
for (int i = 1; i <= p2; i++) { q[i + l + p1 - 1] = q2[i]; }
solve(l, l + p1 - 1, L, mid), solve(l + p1, r, mid + 1, R);
}
signed main() {
cin >> n >> m;
for (int i = 1, x; i <= n; i++) { cin >> x; q[++cnt] = {x, 0, 0, i, 0}; mn = min(mn, x), mx = max(mx, x); }
for (int i = 1, l, r, k; i <= m; i++) { cin >> l >> r >> k; q[++cnt] = {l, r, k, i, 1}; }
solve(1, cnt, mn, mx);
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}