整体二分

一时间竟然不知道怎么切入，我们不妨按照 $\text{OI-Wiki}$ 的思路引入罢。

静态全局第 $k$ 小

Ques 1

询问一次全局第 $k$ 小。

这样的解法是简单的。我们可以直接排序然后访问数组第 $k$ 个位置。也可以考虑二分，但二分要求我们快速知道 $\le x$ 的数有多少个，于是我们就可以使用树状数组（离散化）或者线段树（离散化或动态开点）维护即可。

注意，我们这里称 $kth$ 的算法为 二分，这是因为我们二分 $kth$ 是多少，然后再根据 $\sum\limits_{i=1}^n[a_i\le mid]$ 来判断是 $l=mid$ 还是 $r=mid$。因此，区间 $kth$ 的本质是一种二分。

Ques 2

询问多次全局第 $k$ 小（ $k$ 不同）。

显然，我们仍然可以排个序然后按顺序访问不同的 $k$，但同样，我们可以使用二分的方法。

考虑到二分答案的本质是把一个问题的答案不断缩小直至可以确定。而对于多个问题，这显然也不是问题。我们可以将这许多次询问放在一起，然后统一枚举一个 $mid$ 作为答案，然后根据 $\sum\limits_{i=1}^n[a_i\le mid]$ 的值与 $k$ 的关系将这些问题 分流，偏小的分到左边，偏大的分到右边，然后分别继续枚举各自的 $mid$，再继续分流。这其实在本质上就是一种分治的做法，但是仍然具有二分的枚举答案的特点，简称就是将二分与分治结合起来，通过二分得到的反馈来进行分治。因为二分最多分 $\log n$ 层，而每一层又都是只需要处理 $q$ 个问题，故复杂度就是 $q\log n$。

动态全局第 $k$ 小

这个显然就不区分多次询问还是一次询问了，但是我们仍然分不同的解法。

Sol 1

显然，线段树或者平衡树可以很好地解决这个问题。直接在值域线段树上单点修改整体 $kth$ 即可。

Sol 2

如果我们继续沿着刚刚的思路，把所有的操作放在一起处理，我们能不能解决这个问题呢？

也许你会说，刚刚是没有修改的，我们放在一起可以全部处理询问，但是如果有了修改，我们怎么样确定修改应该被分到左边还是右边呢？显然有修改是会既影响左边又影响右边的。

但是，我们回想一下线段树上 $kth$ 的过程：

1
2
3
4
5
6
int kth(int p,int l,int r,int k){
	if(l == r)	return l;
    int mid = l+r>>1;
    if(s[ls[p]] >= k)	return kth(ls[p], l, mid, k);
    else	return kth(rs[p], mid+1, r, k-s[ls[p]]);
}

我们悄悄的发现了，如果 $kth$ 到了右子树，我们会把左子树的所有东西都减掉，也就是这里的 k-s[ls[p]]。那么，我们在整体二分的时候，能不能按照同样的思路，如果一个修改的值 $\le mid$，或者说这个修改 $x\ k$ 中 $k\le mid$，它显然也会影响到那些被分到右边的查询，但是如果它们被分到右边，那么就有它们的 $ans>mid$，也就是说，无论如何这里的 $k$ 就只能影响这些询问一次了，因此直接在这里减掉 $1$ 即可。同理，如果一个询问要被分到左边，且有一个修改 $x,k$ 中 $k>mid$，那么因为这询问被分到了左边，因此它的 $ans\le mid$，故无论如何右边的那个修改都与它无缘，它们擦肩而过就分道扬镳，再也见不着了。

那么在此基础之上，我们保证分到同一边的操作按照编号大小排序（这是不是有点像归并的逆过程），这就保证了在该操作之前的操作一定会先执行，只要它们被分到了一个地方。

具体地，我们在 solve 函数里面传入参数 L,R,l,r，分别表示操作的左、右端点和目前二分的左、右端点。这样我们令 mid=l+r>>1，作为本次二分的钦定答案。然后：

  • 对于修改操作：
    • 如果有 $k\le mid$，那么我们就进行这次修改（也就是令一个计数器 +1），并且将它分到左边。
    • 否则，我们不进行这次修改，将它放到右边。
  • 对于查询操作：
  • 我们首先看看枚举到这个询问的时候进行了多少次 $\le mid$ 的修改（也就是访问那个计数器），记它为 $t$，然后：
    • 如果有 $t\ge k$，那么，这就说明比 $mid$ 小的数已经比 $k$ 个要多了，这个时候将询问分到左边即可。
    • 否则，小于等于 $mid$ 仍然满足不了 $k$ 个，那么我们将它分到右边，**并且将 $k$ 减去 $t$**。这就是我们刚刚着重讲的那个点。

至于记录答案，我们直接在 $l=r$ 的时候枚举所有的 $i\in [L,R]$，如果 $i$ 操作是询问，就直接把答案赋为 $l$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(int L,int R,int l,int r){
    if(R < L)	return ;
    if(l == r){
        for(int i=L;i<=R;++i)
            if(op[i].type == 2)	op[i].ans = l;
        return ;
    }
    int mid = l+r>>1, cnt1 = 0, cnt2 = 0, cnt = 0;
    for(int i=L;i<=R;++i)
        if(op[i].type == 2){
        	if(cnt < op[i].c)	op[i].c -= cnt, q[++cnt2] = op[i];
            else	p[++cnt1] = op[i];
        }else{
            if(op[i].c <= mid)	++cnt, p[++cnt1] = op[i];
            else	q[++cnt2] = op[i];
        }
    for(int i=1;i<=cnt1;++i)	op[i+L-1] = p[i];
    for(int i=1;i<=cnt2;++i)	op[i+L+cnt1-1] = q[i];
    solve(L, L+cnt1-1, l, mid), solve(L+cnt2, R, mid+1, r);
}

静态区间第 $k$ 小

这里虽然是静态，但是每一次查询的区间并不一样，因此我们需要记录一个类似于前缀和的东西来帮助我们完成这个询问。

可持久化线段树

我们使用动态开点线段树，然后对于每个位置 $i$ 都开一个线段树，它是基于第 $i-1$ 棵线段树的基础上加上一个点产生的。注意到单点修改只会有 $\log n$ 次，然后在查询区间的时候我们使用 $s_r-s_{l-1}$ 的差分方法就可以直接在线段树上求区间 $kth$ 了。

二分答案

同样地，我们可以使用二分来解决问题。根据上面的思路，我们不难想到这里区间查询的解题思路：

首先，修改是没有用的，我们直接接着全局静态查询的思路来。全局静态查询需要我们知道全局小于等于它的是多少，但是这里我们改成了区间，这就可以了。如果不能理解，我们可以先考虑如果只有一个询问怎么二分，显然地，我们直接枚举 $mid$ 并询问 $\le mid$ 的有多少个，然后根据这个结果进行缩小区间操作即可。询问多了就把询问分流即可。

但是我们注意到有一个区间求小于等于某个数的数有多少个，这我们使用树状数组对于每个区间每次加入后再清空，这就显得很冗杂，因为我们明明完全可以在主席书上直接二分来减少一个 $\log$ 的，但是不急，虽然这个方法在现在开起来并不优，但是这方法具有很高的可拓展性。这是因为给定初始数组可以被看做在刚开始进行了 $n$ 次修改。而我们二分的时候把修改放到询问中间来，这就可以完全兼容后面待修的做法。

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
struct BIT{
    int b[N];
    #define lowbit(x) (x&-x)
    void update(int x,int k);
    int query(int x);
    #undef lowbit
}t;
void solve(int L,int R,int l,int r){
    if(R < L)	return ;
    if(l == r){
        for(int i=L;i<=R;++i)
            op[i].ans = l;
        return ;
    }
    int mid = l+r>>1, cnt1 = 0, cnt2 = 0;
    for(int i=L;i<=R;++i)
        if(op[i].type == 1){
            if(op[i].c <= mid)	update(op[i].loca, 1), p[++cnt1] = op[i];
            else	q[++cnt2] = op[i];
        }else{
            int t = query(op[i].r) - query(op[i].l-1);
            if(t >= op[i].c)	p[++cnt1] = op[i];
            else	op[i].c -= t, q[++cnt2] = op[i];
        }
   	for(int i=1;i<=cnt1;++i)
        if(op[i].type == 1)	update(op[i].loca, -1);
   	for(int i=1;i<=cnt1;++i)	op[i+L-1] = p[i];
    for(int i=1;i<=cnt2;++i)	op[i+L+cnt1-1] = q[i];
    solve(L, L+cnt1-1, l, mid), solve(L+cnt1, R, mid+1, r);
}

其中，值得注意的是每次进入函数我们需要判断 $R<L$，这是因为如果所有的操作都被分配到一边，那么就会出现 solve(L, L-1, l, mid) 或者 solve(R+1, R, mid+1, r)，如果不进行判断就会产生错误。

动态区间第 $k$ 小

于是我们来看看终极问题：动态区间第 $k$ 小。这就需要 “解决动态区间第 $k$ 的三种方法”。

Sol1

我们仍然可以使用数据结构草过去。但是这次的数据结构就十分高级了：树套树。

这里，我们使用树状数组套线段树。

修改操作

因为外层是树状数组，我们在 $x$ 这个地方把 $a_x$ 变为 $y$ 这个操作，会影响到所有在 for(int i=x;i<=n;i+=lowbit(i)) 这个语句中遍历到的 $i$，因此，在这些地方我们都需要对线段树进行修改。具体地，这个线段树是值域线段树，我们把原来的 $a_x$ 删除，然后再加上 $y$ 即可。因此，一次操作需要操作 $\log n$ 次线段树，也就是复杂度为 $O(\log ^2 n)$。

查询操作

同样地，根据树状数组的定义，我们想要知道 $[1,r]$ 中有多少个数，我们就需要加上所有 for(int i=r;i;i-=lowbit(i)) 语句遍历到的 $i$ 所在线段树的数。然后，我们还要知道 $[1,l-1]$ 有多少个数，把上面的 $r$ 改成 $l-1$ 即可。然后我们把这两个值相减，就能够得到当前的节点上 $[l,r]$ 有多少个数。

于是，我们仍然在线段树上二分，但是我们这次同时在 $2\log n$ 棵线段树上进行二分，然后每一次我们需要知道它们的左儿子有多少个数，于是我们需要 $O(\log n)$ 求出这个 $sum$ 来跟 $k$ 作比较。这就完成了一次二分的过程，然后我们就直接继续二分即可。这样，一次查询的复杂度就是 $O(log^2 n)$ 的。

这样，我们就得到了一个 $O((n+q)log^2 n)$ 的优秀做法。它本质上是使用外层的树状数组来维护数列，然后内层线段树来完成查询操作。但是，它的空间复杂度实在是太高了，因为有可能有 $O(n)$ 次修改，然后我们每一次需要修改 $O(\log n)$ 棵线段树，每棵线段树有可能修改 $O(\log n)$ 个节点，这样空间复杂度达到了 $O(n\log ^2 n)$，令我无法接受（当然题目可以接受）。

Code

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
int n, a[N], b[N<<1], m, cnt;
struct opt{
	char type;
	int l, r, k;
}op[N];

int root[N], s[N<<7], ls[N<<7], rs[N<<7], idx;
void update(int &p,int l,int r,int x,int k){
	if(!p)	p = ++idx;
	s[p] += k;
	if(l == r)	return ;
	int mid = l+r>>1;
	if(x <= mid)	update(ls[p], l, mid, x, k);
	else	update(rs[p], mid+1, r, x, k);
}

#define lowbit(x) (x&-x)
void modify(int x,int v,int k){
	for(int i=x;i<=n;i+=lowbit(i))
		update(root[i], 1, cnt, v, k);
}
int n1, n2, t1[N], t2[N];
int kth(int l,int r,int k){
	if(l == r)	return l;
	int sum = 0;
	for(int i=1;i<=n1;++i)	sum -= s[ls[t1[i]]];
	for(int i=1;i<=n2;++i)	sum += s[ls[t2[i]]];
	int mid = l+r>>1;
	if(sum < k){
		for(int i=1;i<=n1;++i)	t1[i] = rs[t1[i]];
		for(int i=1;i<=n2;++i)	t2[i] = rs[t2[i]];
		return kth(mid+1, r, k - sum);
	}else{
		for(int i=1;i<=n1;++i)	t1[i] = ls[t1[i]];
		for(int i=1;i<=n2;++i)	t2[i] = ls[t2[i]];
		return kth(l, mid, k);
	}
}
void init(int l,int r,int k){
	n1 = n2 = 0;
	for(int i=r;i;i-=lowbit(i))	t2[++n2] = root[i];
	for(int i=l-1;i;i-=lowbit(i))	t1[++n1] = root[i];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)	cin>>a[i], b[++cnt] = a[i];
	for(int i=1;i<=m;++i){
		cin>>op[i].type;
		if(op[i].type == 'C'){
			cin>>op[i].l>>op[i].k;
			b[++cnt] = op[i].k;
		}else	cin>>op[i].l>>op[i].r>>op[i].k;
	}
	sort(b+1, b+1+cnt);
	cnt = unique(b+1, b+1+cnt) - b - 1;
	for(int i=1;i<=n;++i)	a[i] = lower_bound(b+1, b+1+cnt, a[i]) - b;
	for(int i=1;i<=m;++i)
		if(op[i].type == 'C')	op[i].k = lower_bound(b+1, b+1+cnt, op[i].k) - b;
	for(int i=1;i<=n;++i)	modify(i, a[i], 1);
	for(int i=1;i<=m;++i){
		if(op[i].type == 'C'){
			modify(op[i].l, a[op[i].l], -1);
			a[op[i].l] = op[i].k;
			modify(op[i].l, a[op[i].l], 1);
		}else	init(op[i].l, op[i].r, op[i].k), cout<<b[kth(1, cnt, op[i].k)]<<endl;
	}
	return 0;
}

代码还是不难写的。

Sol2

另外，如果你十分熟悉 $\text{Ynoi}$ 的题目，这道题可以使用分块来完成。

谁说就没有分块套分块呢。

按照树套树的思路，我们来一个分块套分块就可以了，具体地细节我还没写（bushi。

Sol3

整体二分。我们直接将第二个问题：动态区间 $kth$ 中的操作改一下，再查询中加入修改操作即可。

例题