就 WA 这了。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int B = 400 + 10;
int n, m, mx, a[N], b[N];
int blk, tot, bel[N], s[B], t[B];

void init(){
	blk = sqrt(n), tot = n / blk + (n % blk ? 1 : 0);
	for(int i=1;i<=n;i++)
		bel[i] = (i - 1) / blk + 1;
	for(int i=1;i<=tot;i++)
		s[i] = (i - 1) * blk + 1, t[i] = min(n, i * blk);
	for(int i=1;i<=n;i++)
		b[i] = a[i];
	for(int i=1;i<=tot;i++)
		sort(b + s[i], b + 1 + t[i]);
}

void update(int x, int k){
	a[x] = k;
	for(int i=s[bel[x]];i<=t[bel[x]];i++)
		b[i] = a[i];
	sort(b + s[bel[x]], b + 1 + t[bel[x]]);
}

int calc(int l, int r, int k){
	int cnt = 0;
	if(bel[l] == bel[r]){
		for(int i=l;i<=r;i++)
			cnt += (a[i] <= k);
		return cnt;
	}
	for(int i=l;i<=t[bel[l]];i++)
		cnt += (a[i] <= k);
	for(int i=bel[l]+1;i<bel[r];i++)
		cnt += upper_bound(b + s[i], b + 1 + t[i], k) - b - s[i];
	for(int i=s[bel[r]];i<=r;i++)
		cnt += (a[i] <= k);
	return cnt;
}

int query(int s, int t, int k){
	int l = 0, r = mx, res;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(calc(s, t, mid) < k)
			l = mid + 1;
		else
			res = mid, r = mid - 1;
	}
	return res;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
		scanf("%d", &a[i]), mx = max(mx, a[i]);
	init();
	while(m--){
		char op[4];
		int l, r, k;
		scanf("%s", op);
		if(op[0] == 'C'){
			scanf("%d%d", &l, &k);
			update(l, k);
		}
		else{
			scanf("%d%d%d", &l, &r, &k);
			printf("%d\n", query(l, r, k));
		}
	}
	return 0;
}