蜜汁整体二分——区间 kth

板子题（或许？）：

link，点击这里喵。
小声：第一次学整体二分，有误请见谅。

题意：可持久化线段树 2——区间 kth.

如题，给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[l,r]$ 查询其区间内的第 $k$ 小值。

解法:

梦幻：如果我们能够维护一个数组 $cnt[i][j]$，表示下标小于 $i$，值小于 $j$ 的数的个数就好了啊。
这样只需要二分 $j$ 就能的出来了。
形式化的：
$$cnt[i][j]=\sum _{e=i}^n[a_e<j]$$
可这，空间炸了，时间也炸了。

思考一下权值线段树套区间和线段树的套路，发现是完全可行的，外层维护值域，内层维护下标。

思考一下权值线段树的作用，发现其仅仅是执行一个二分值域的操作，这非常类似于二分。

由于是离线的，我们完全可以把外层的权值线段树过掉！具体的，我们像权值线段树那样在每一个值域区间只维护那个值域区间内的点，如：

void dfs(int low, int high) {}

$low$ 维护最低值域，$high$ 维护最高值域，在这一层中，我们维护的点 $a.v\in [low,high)$。

同时，我们也应当像权值线段树那样支持询问，模仿其思路，从上往下将询问分配到每一个区间，很像平衡树 $rank\to val$ 操作。

具体的，将他们两个合并在一个数组中就好了。

代码 time ~

#include <bits/stdc++.h>
using namespace std;#define inf 0x3f3f3f3f
typedef long long lnt;struct my_stream {int x;operator lnt() {scanf("%d", &x);return x;}
} __rp_read;
#define input() __rp_readconst int N = 1e6 + 20;#define lowbit(x) ((x) & -(x))
struct tray {const static int ys = 10;int g[N];void update(int b, int k) {b += ys;while (b < N) g[b] += k, b += lowbit(b);}int query(int b) {b += ys;int tp = 0;while (b) tp += g[b], b -= lowbit(b);return tp;}
} t;struct DQ {int id, x, y, k; // when id == 0, x means position, y means value
} d[N], tp[N];       // when id == 1, [x, y) means [l, r)int ans[N];void dfs(int low, int high, int bg, int ed) { // logVif (bg == ed) return;if (low == high - 1) {for (int i = bg; i < ed; ++i) //if (d[i].id != -1)        //ans[d[i].id] = low;return;}int mid = (low + high) >> 1, lp = bg, rp = ed;for (int i = bg; i < ed; ++i) {if (d[i].id != -1) continue;if (d[i].y < mid) tp[lp++] = d[i], t.update(d[i].x, 1);else if (d[i].id == -1) tp[--rp] = d[i];}for (int i = bg; i < ed; ++i) {if (d[i].id == -1) continue;int cnt = t.query(d[i].y - 1) - t.query(d[i].x - 1);if (d[i].k <= cnt) tp[lp++] = d[i];else tp[--rp] = d[i], tp[rp].k -= cnt;}for (int i = bg; i < lp; ++i) // clean BITif (tp[i].id == -1)       //t.update(tp[i].x, -1);copy(tp + bg, tp + ed, d + bg);dfs(low, mid, bg, lp);dfs(mid, high, lp, ed);
}int n, m;int main() { //n = input(), m = input();int top = 0;for (int i = 0; i < n; ++i) {d[top++] = {-1, i, input(), 0};}for (int i = 0; i < m; ++i) {int l = input(), r = input(), k = input();d[top++] = {i, l - 1, r, k};}dfs(0, inf, 0, n + m);for (int i = 0; i < m; ++i) {printf("%d\n", ans[i]);}return 0;
}