求助dalao！本地跑的贼快，交上去全T

#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e6 + 10;
int n, m, a[N], root[N << 2];
struct FHQ_Treap {
	int tot = 0;
	struct node {
		int l, r;
		int siz, key, val;
	}tr[N];
	FHQ_Treap () {
		tot = 0;
		memset (tr, 0, sizeof (tr));
	}
	
	int newnode (int v) {
		tr[++tot].key = rand();
		tr[tot].siz = 1; tr[tot].val = v;
		return tot;
	}
	
	int pushup (int k) {
		tr[k].siz = tr[tr[k].l].siz + tr[tr[k].r].siz + 1;
	}
	
	void split (int nd, int k, int &x, int &y) {
		if (!nd) x = y = 0;
		else {
			if (tr[nd].val <= k) {
				x = nd;
				split (tr[x].r, k, tr[x].r, y);
			}
			else {
				y = nd;
				split (tr[y].l, k, x, tr[y].l);
			}
			pushup (nd);
		}
	}
	
	void merge (int &root, int x, int y) {
		if (!x || !y) { root = x + y; return ; }
		if (tr[x].key < tr[y].key) {
			root = x;
			merge (tr[root].r, tr[x].r, y);
			pushup (x);
		}
		else {
			root = y;
			merge (tr[root].l, x, tr[y].l);
			pushup (y);
		}
	}
	
	void ins (int &root, int k) {
		int x, y, z = newnode (k);
		split (root, k, x, y);
		merge (x, x, z); merge (root, x, y);
	}
	
	void del (int &root, int k) {
		int x, y, c, d;
		split (root, k, x, y);
		split (x, k - 1, c, d);
		merge (d, tr[d].l, tr[d].r);
		merge (c, c, d); merge (root, c, y);
	}
	
	int rank (int &root, int k) {
		int x, y, s = 0;
		split (root, k - 1, x, y);
		s = tr[x].siz + 1;
		merge (root, x, y);
		return s;
	}
}F;

void change (int nd, int l, int r, int x, int ov, int nv) {
	F.del(root[nd], ov); F.ins(root[nd], nv);
	if (l == r) return ;
	int mid = l + r >> 1;
	if (x <= mid) change (nd<<1, l, mid, x, ov, nv);
	else change (nd<<1|1, mid + 1, r, x, ov, nv);
}

int getrank (int nd, int l, int r, int x, int y, int k) {
	if (l == x && r == y) return F.rank(root[nd], k) - 1;
	int mid = l + r >> 1;
	if (y <= mid) return getrank (nd<<1, l, mid, x, y, k);
	if (x > mid) return getrank (nd<<1|1, mid + 1, r, x, y, k);
	return getrank (nd<<1, l, mid, x, mid, k) + getrank (nd<<1|1, mid + 1, r, mid + 1, y, k);
}

int findval (int l, int r, int k) {
	int lb = 0, rb = (int)(1e9), mid, tmp1, tmp2;
	while (lb <= rb) {
		mid = lb + rb >> 1;
		tmp1 = getrank (1, 1, n, l, r, mid);
		tmp2 = getrank (1, 1, n, l, r, mid + 1);
		if (tmp1 < k && tmp2 >= k) return mid;
		if (tmp1 >= k) rb = mid - 1;
		else lb = mid + 1;
	}
}

int main () {
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) {
		scanf ("%d", &a[i]);
		change (1, 1, n, i, 0, a[i]);
	}
//	for (int i = 1; i <= n * 2; i ++ ) cout << root[i] << " ";
//	cout << endl;
	for (int i = 1; i <= m; i ++ ) {
		char opt; int x, y, k;
		cin >> opt;
		scanf ("%d%d", &x, &y);
		switch (opt) {
			case 'C': change (1, 1, n, x, a[x], y); a[x] = y; break;
			case 'Q': scanf ("%d", &k); printf ("%d\n", findval (x, y, k)); break;
		}
	}
	return 0;
}