已验证，和空间大小无关。但是仍然WA50（后十个点）. 使用动态主席树做的（大概指的是第一篇题解那种），整了一天...

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int N,M,a[maxn],ls[maxn],lstop=0,ftop=0,numf=0,root[maxn],st1[maxn],st2[maxn],stop1,stop2;
struct nodein{int a,b,c,d;}rd[maxn];
struct node{int v,l,r;}f[100*maxn<<3];
int lowbit(int t){return t&(-t);}
int qd(){
	int rt=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
	return rt;
}
void change(int &t,int l,int r,int p,int v){
	if(!t)  t=++numf;
//	printf("C %d %d %d %d %d\n",t,l,r,p,v);
	f[t].v+=v;
	if(l==r)  return;
	int m=(l+r)>>1;
	if(p<=m)  change(f[t].l,l,m,p,v);
	else  change(f[t].r,m+1,r,p,v);
}
void changep(int p,int v2){//p get his;k get val-pos to add v2
	int k=lower_bound(ls+1,ls+lstop+1,a[p])-ls;
//	printf("C %d %d %d\n",p,k,v2);
	for(;p<=N;p+=lowbit(p)){
//		printf("p=%d\n",p);
		change(root[p],1,lstop,k,v2);
	}
}//space:nlogn,t0==t
int ask(int l,int r,int p){
//	printf("A %d %d %d\n",l,r,p);
	if(l==r)  return l;
	int dt=0,m=(l+r)>>1;
	for(int i=1;i<=stop1;i++)  dt+=f[f[st1[i]].l].v;
	for(int i=1;i<=stop2;i++)  dt-=f[f[st2[i]].l].v;
	if(p<=dt){
		for(int i=1;i<=stop1;i++)  st1[i]=f[st1[i]].l;
		for(int i=1;i<=stop2;i++)  st2[i]=f[st2[i]].l;
		return ask(l,m,p);
	}
	else{
		for(int i=1;i<=stop1;i++)  st1[i]=f[st1[i]].r;
		for(int i=1;i<=stop2;i++)  st2[i]=f[st2[i]].r;
		return ask(m+1,r,p-dt);
	} 
}
int askp(int l,int r,int p){
	stop1=stop2=0;
	for(int i=r;i;i-=lowbit(i))  st1[++stop1]=root[i];
	for(int i=l-1;i;i-=lowbit(i))  st2[++stop2]=root[i];
	return ask(1,lstop,p);
}
int main(){
	N=qd(),M=qd();
	for(int i=1;i<=N;i++)  a[i]=ls[++lstop]=qd();
	for(int i=1;i<=M;i++){
		scanf(" %c",&rd[i].a);
//		printf("read c:%c c->d:%d\n",(char)rd[N+i].a,rd[N+i].a);
		if(rd[i].a=='Q')  rd[i].b=qd(),rd[i].c=qd(),rd[i].d=qd();
		else rd[i].b=qd(),rd[i].c=ls[++lstop]=qd();
	}
	sort(ls+1,ls+lstop+1);
	lstop=unique(ls+1,ls+lstop+1)-ls-1;
//	for(int i=1;i<=lstop;i++)  printf("%d ",ls[i]);
//	printf("\n");
	for(int i=1;i<=N;i++)  changep(i,1);
//		printf("T\n");
	for(int i=1;i<=M;i++){
		if(rd[i].a=='Q')  printf("%d\n",ls[askp(rd[i].b,rd[i].c,rd[i].d)]);
		else{
			changep(rd[i].b,-1);
			a[rd[i].b]=rd[i].c;
			changep(rd[i].b,1);
		}
	}
	return 0;
}