RT，WA了#5和#11~#20

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define getchar() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,1<<21,stdin),_p1==_p2)?EOF:*_p1++)
char buf[1 << 21], *_p1 = buf, *_p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

#define GetSum(p) (p ? p->sum : 0)
#define Lc(p) (p ? p->l : 0)
#define Rc(p) (p ? p->r : 0)
struct Node {
	int sum;
	Node *l, *r;
};
Node nd[17000005], *p1[33], *p2[33];
int top, pcnt1, pcnt2;
queue <Node*> que;
struct Segtree {
	Node *_root[100005];
	inline void Modify(Node *&p1, Node *p2, int l, int r, int v, int ncnt) {
		//printf("%d %d\n", l, r);
		if (!p1) {
			if (que.empty()) p1 = &nd[++top];
			else {
				p1 = que.front();
				que.pop();
			}
			p1->sum = GetSum(p2);
		}
		if (l == r) {
			p1->sum += ncnt;
			return;
		}
		register int mid = l + r >> 1;
		if (v <= mid) Modify(p1->l, Lc(p2), l, mid, v, ncnt);
		else Modify(p1->r, Rc(p2), mid + 1, r, v, ncnt);
		p1->sum = GetSum(p1->l) + GetSum(p1->r);
		/*
		if (p1->sum == 0 && !p1->l && !p1->r) {
			que.push(p1);
			p1 = NULL;
		}
		*/
	}
	inline int Query(int l, int r, int k) {
		if (l == r) return l;
		register int mid = l + r >> 1, cnt = 0;
		for (register int i = 1;i <= pcnt2;i++) cnt += GetSum(Lc(p2[i]));
		for (register int i = 1;i <= pcnt1;i++) cnt -= GetSum(Lc(p1[i]));
		if (k <= cnt) {
			for (register int i = 1;i <= pcnt1;i++) p1[i] = Lc(p1[i]);
			for (register int i = 1;i <= pcnt2;i++) p2[i] = Lc(p2[i]);
			return Query(l, mid, k);
		} else {
			for (register int i = 1;i <= pcnt1;i++) p1[i] = Rc(p1[i]);
			for (register int i = 1;i <= pcnt2;i++) p2[i] = Rc(p2[i]);
			return Query(mid + 1, r, k - cnt);
		}
	}
};
Segtree sgt;
struct Operation {
	int x, y, k;
};
int n, m, a[100005], vtop, b[200005];
Operation opt[100005];

inline int Lowbit(int x) {
	return x & -x;
}

inline void Read() {
	n = qread(); m = qread();
	for (register int i = 1;i <= n;i++) b[++vtop] = a[i] = qread();
	for (register int i = 1;i <= m;i++) {
		register char c = getchar();
		while (c != 'Q' && c != 'C') c = getchar();
		if (c == 'Q') {
			opt[i].x = qread();
			opt[i].y = qread();
			opt[i].k = qread();
		} else {
			opt[i].x = qread();
			b[++vtop] = opt[i].y = qread();
		}
	}
}

inline void Prefix() {
	sort(b + 1, b + vtop + 1);
	vtop = unique(b + 1, b + vtop + 1) - b - 1;
	for (register int i = 1;i <= n;i++) a[i] = lower_bound(b + 1, b + vtop + 1, a[i]) - b;
	for (register int i = 1;i <= m;i++) {
		if (!opt[i].k) opt[i].y = lower_bound(b + 1, b + vtop + 1, opt[i].y) - b;
	}
}

inline void Modify(int i, int v, int x) {
	for (register int j = i;j <= n;j += Lowbit(j)) sgt.Modify(sgt._root[j], sgt._root[j - Lowbit(j)], 1, vtop, v, x);
}

inline int Query(int l, int r, int k) {
	pcnt1 = 0; pcnt2 = 0;
	for (register int j = r;j >= 1;j -= Lowbit(j)) p2[++pcnt2] = sgt._root[j];
	for (register int j = l - 1;j >= 1;j -= Lowbit(j)) p1[++pcnt1] = sgt._root[j];
	return sgt.Query(1, vtop, k);
}

inline void Solve() {
	for (register int i = 1;i <= n;i++) Modify(i, a[i], 1);
	for (register int i = 1;i <= m;i++) {
		//printf("%d\n", i);
		if (opt[i].k) {
			printf("%d\n", b[Query(opt[i].x, opt[i].y, opt[i].k)]);
		}
		else {
			Modify(opt[i].x, a[opt[i].x], -1);
			Modify(opt[i].x, opt[i].y, 1);
			a[opt[i].x] = opt[i].y;
		}
	}
}

int main() {
	//printf("%.2lf", sizeof(nd) / 1000000.0);
	Read();
	Prefix();
	Solve();
	#ifndef ONLINE_JUDGE
	while (1);
	#endif
	return 0;
}