引入

我们看一道题：

给定一个长度为 $n(n≤50000)n(n\leq 50000)$ 的数组 $a_1 , a_2 , ... , a_n$ 和 $q(q≤10,000)q\ ( q \leq 10,000 )$ 次询问，每次询问：

$Q$ $i$ $j$ $k$ 表示区间 $[i, j]$ 中第 $k$ 小的数是多少，并输出这个数。
$C$ $i$ $t$ 表示将第 $i$ 个数改为 $t$ 。

我们会发现这是一道主席树的题。

这道题很明显能用主席树来完成，但我们有其他更加简便的算法，于是我们来看看这个新的算法——整体二分。

思路

对于单个查询我们可以二分解决，但是查询往往是一系列的，这也就导致了时间过长，于是我们来想想如何解决。

我们还是用二分的思想来解决，于是我们可以将所有的操作（修改和查询）一起来二分。

每次二分都可以完成多次操作，所以就不会有同一个地方被多次查询（或修改）操作。

可以看下代码理解（上面题的，有注释）：

struct node {int a, b, c, d, tp, sum;//tp记录当前是哪一种操作//若tp = 1，则是插入操作，a代表第几个数插入，b代表插入的值//若tp = 2，则是删除操作，a代表第几个数删除，b代表删除的值//若tp = 3，则是查询操作，a代表查询的左端点，b代表查询的右端点，c代表所求的k，d代表当前是第几次查询，sum代表若二分到l, r是，再a, b区间里面值域再1, l - 1的数的个数
} q[1000005], q1[1000005], q2[1000005];
void divide(int hd, int tl, int l, int r) {if (hd > tl || l == r) {//如果我们现在这个二分里面没有任何操作或者已经无法二分了for (int i = hd; i <= tl; i++)if (q[i].tp == 3)ans[q[i].d] = l;//这说明当前的答案已经找到return ;}int mid = (l + r) / 2;for (int i = hd; i <= tl; i++) {//将每个操作二分if (q[i].tp == 1 && q[i].b <= mid)add(q[i].a, 1);//我们用树状数组维护值域为l, mid的数的个数if (q[i].tp == 2 && q[i].b <= mid)add(q[i].a, -1);if (q[i].tp == 3)tmp[i] = find(q[i].b) - find(q[i].a - 1);//这里是判断再查询的区间里面有多少个值域在l, mid的数}for (int i = hd; i <= tl; i++) {//清空树状数组，注意不能全部清空，要不会TLEif (q[i].tp == 1 && q[i].b <= mid)add(q[i].a, -1);if (q[i].tp == 2 && q[i].b <= mid)add(q[i].a, 1);}int cnt1 = 0, cnt2 = 0;for (int i = hd; i <= tl; i++) {if (q[i].tp == 3) {if (q[i].sum + tmp[i] < q[i].c)//如果我们发现值域为1, mid的个数要比我们需要的少，我们就将它放入值域为mid + 1, r里面继续二分q2[++cnt2] = q[i], q2[cnt2].sum += tmp[i];else//否则就放到l, mid里面二分q1[++cnt1] = q[i];}else {if (q[i].b <= mid)//如果这个修改操作是在l, mid的区间里的，那就放在l, mid里面二分q1[++cnt1] = q[i];else//否则就放到mid + 1, r里面二分q2[++cnt2] = q[i];}}for (int i = hd; i < hd + cnt1; i++)q[i] = q1[i - hd + 1];for (int i = hd + cnt1; i < hd + cnt1 + cnt2; i++)q[i] = q2[i - hd - cnt1 + 1];//我们将操作分为两组divide(hd, hd + cnt1 - 1, l, mid);divide(hd + cnt1, tl, mid + 1, r);
}
int main() {scanf("%d%d", &n, &Q);for (int i = 1; i <= n; i++)scanf("%d", &num[i]),++cnt, q[cnt].a = i, q[cnt].b = num[i], q[cnt].tp = 1;//这里是插入操作for (int i = 1, a, b, c; i <= Q; i++) {if (in() == 'Q')scanf("%d%d%d", &a, &b, &c),++cnt, q[cnt].a = a, q[cnt].b = b, q[cnt].c = c,q[cnt].d = ++qcnt, q[cnt].tp = 3;else {scanf("%d%d", &a, &b);++cnt, q[cnt].a = a, q[cnt].b = num[a], q[cnt].tp = 2;++cnt, q[cnt].a = a, q[cnt].b = b, q[cnt].tp = 1;//我们把修改操作改成删除和插入操作num[a] = b;}}divide(1, cnt, 0, 1e9);for (int i = 1; i <= qcnt; i++)printf("%d\n", ans[i]);return 0;
}