整体二分本地AC， 提交RE

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int MAX = 1e6 + 70;
int n, m, a[MAX], tree[MAX], b[MAX], ans[MAX], num, tot;
struct made {
	int x, y, k, val, id;
}ask[MAX], ql[MAX], qr[MAX];
int lowbit(int x) {
	return x & (-x);
}
int find(int x) {
	int ans = 0;
	for(int i = x; i; i -= lowbit(i)) ans += tree[i];
	return ans;
}
int add(int x, int val) { for(int i = x; i <= 1e6; i += lowbit(i)) tree[i] += val; }
void slove(int lval, int rval, int l, int r) {
	int mid = (lval + rval) / 2;
	int lt = 0, rt = 0;
	if(l > r) return ;
	if(lval == rval) {
		for(int i = l; i <= r; i++) 
			if(ask[i].k != 0 && ask[i].id) ans[ask[i].id] = lval;
		return ;
	}
	for(int i = l; i <= r; i++)	{
		if(ask[i].k == 0) { // 修改操作 
			if(ask[i].y <= mid) {
				ql[++lt] = ask[i];
				add(ask[i].x, ask[i].val);
			}  else qr[++rt] = ask[i];
		} else { // 查询操作 
			int num = find(ask[i].y) - find(ask[i].x - 1);
			if(num >= ask[i].k) {
				ql[++lt] = ask[i];
			} else {
				qr[++rt] = ask[i];
				qr[rt].k -= num;
			}
		}
	}
	for(int i = 1; i <= lt; i++) {
		if(ql[i].k == 0) add(ql[i].x, -ql[i].val);
	}
	for(int i = 1; i <= lt; i++) ask[l + i - 1] = ql[i];
	for(int i = 1; i <= rt; i++) ask[l + lt - 1 + i] = qr[i];
	slove(lval, mid, l, l + lt - 1);
	slove(mid + 1, rval, l + lt, r);
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		b[++tot] = a[i];
		ask[++num] = (made){i, a[i], 0, 1, 0};
	} 
	for(int i = 1; i <= m; i++) {
		char ch; cin>>ch;
		if(ch == 'Q') { 
			int x, y, k; scanf("%d%d%d", &x, &y, &k);
			ask[++num] = (made){x, y, k, 0, i};
		} else if(ch == 'C') {
			int x, y;
			scanf("%d%d", &x, &y); 
			b[++tot] = y;
			ask[++num] = (made){x, a[x], 0, -1, 0};
			ask[++num] = (made){x, y, 0, 1, 0};
			a[x] = y;
		}
	}
	sort(b + 1, b + 1 + tot);
	for(int i = 1; i <= num; i++) 
		if(ask[i].k == 0) ask[i].y = lower_bound(b + 1, b + 1 + tot, ask[i].y) - b;
	for(int i = 1; i <= m; i++) ans[i] = -1;
	slove(0, 1e5, 1, num);
	for(int i = 1; i <= m; i++) {
		if(ans[i] != -1) printf("%d\n", b[ans[i]]);
	}
	return 0;
}