https://www.luogu.com.cn/record/98265518
救救孩子吧

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, P = 355;
namespace v { int limit, blk, cnt, pos[N], L[P], R[P]; } 
struct range_sqrtdec {
	int a[N], sum[P];
	void update(int x, int val) { a[x] += val, sum[v::pos[x]] += val; }
} D[P];
int n, q, blk, cnt, l[N], r[N], k[N], qwq, a[N], tmp[N], t[N], pos[N], L[P], R[P];
char opt[N];
void build() {
	v::limit = 1e5, v::blk = sqrt(v::limit), v::cnt = v::limit / v::blk + bool(v::limit % v::blk);
	for (int i = 1; i <= v::cnt; i ++) {
		v::L[i] = v::R[i - 1] + 1, v::R[i] = min(i * v::blk, v::limit), D[i] = D[i - 1];
		for (int j = v::L[i]; j <= v::R[i]; j ++) v::pos[j] = i, D[i].update(a[j], 1);
	}
}
void update(int x, int val) {
	for (int i = pos[x]; i <= cnt; i ++) D[pos[x]].update(a[x], -1), D[pos[x]].update(val, 1);
	a[x] = val;
}
int sortKth(int l, int r, int k) {
	for (int i = l; i <= r; i ++) tmp[i] = a[i];
	return sort(a + l, a + 1 + r), a[l + k - 1];
}
int Kth(int l, int r, int k) {
	int lp = pos[l], rp = pos[r], res = -1;
	if (lp == rp) return sortKth(l, r, k);
	for (int i = l; i <= R[lp]; i ++) D[rp - 1].update(a[i], 1);
	for (int i = L[rp]; i <= r; i ++) D[rp - 1].update(a[i], 1);
	for (int i = 1; i <= v::cnt; i ++) {
		if (k > D[rp - 1].sum[i] - D[lp].sum[i]) k -= D[rp - 1].sum[i] - D[lp].sum[i];
		else for (int j = v::L[i]; j <= v::R[i]; j ++)
			if ((k -= D[rp - 1].a[i] - D[lp].a[i]) <= 0) { res = j; goto Readd; } 
	} Readd:
	for (int i = l; i <= R[lp]; i ++) D[rp - 1].update(a[i], -1);
	for (int i = L[rp]; i <= r; i ++) D[rp - 1].update(a[i], -1);
	return res;
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i ++)
	    cin >> a[i], t[++ qwq] = a[i];
	for (int i = 1; i <= q; i ++) {
	    cin >> opt[i];
	    if (opt[i] == 'Q') cin >> l[i] >> r[i] >> k[i];
	    if (opt[i] == 'C') cin >> l[i] >> k[i], t[++ qwq] = k[i]; 
	}
	sort(t + 1, t + 1 + qwq), qwq = unique(t + 1, t + 1 + qwq) - t - 1;
	for (int i = 1; i <= n; i ++)
	    a[i] = lower_bound(t + 1, t + 1 + qwq, a[i]) - t;
	build();
	for (int i = 1; i <= q; i ++) {
	   	if (opt[i] == 'C') k[i] = lower_bound(t + 1, t + 1 + qwq, k[i]) - t;
	    if (opt[i] == 'Q') cout << t[Kth(l[i], r[i], k[i])] << '\n';
	    if (opt[i] == 'C') update(l[i], k[i]); 
	}
	return 0;
}