#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],b[200010],rt[100010],L,cnt,T[2][210],c0,c1;
char opt;
struct node{int ls,rs,s;}tree[40000010];
struct ask{int opt,l,r,k,p,t;}q[100010];
int read()
{
	int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
void update(int &root,int l,int r,int x,int s)
{
	if(!root) root=++cnt;
	tree[root].s+=s;
	if(l==r) return;
	int mid=(l+r)/2;
	if(x<=mid) update(tree[root].ls,l,mid,x,s);
	  else update(tree[root].rs,mid+1,r,x,s);
}
void change(int x,int s)
{
	int k=lower_bound(b+1,b+L+1,a[x])-b;
	for(;x<=n;x+=x&(-x)) update(rt[x],1,L,k,s);
}
int query(int l,int r,int k)
{
	if(l==r) return l;
	int mid=(l+r)/2,s=0;
	for(int i=1;i<=c1;i++) s+=tree[tree[T[1][i]].ls].s;
	for(int i=1;i<=c0;i++) s-=tree[tree[T[0][i]].ls].s;
	if(k<=s)
	{
		for(int i=1;i<=c1;i++) T[1][i]=tree[T[1][i]].ls;
		for(int i=1;i<=c0;i++) T[0][i]=tree[T[0][i]].ls;
		return query(l,mid,k);
	}
	else
	{
		for(int i=1;i<=c1;i++) T[1][i]=tree[T[1][i]].rs;
		for(int i=1;i<=c0;i++) T[0][i]=tree[T[0][i]].rs;
		return query(mid+1,r,k-s);
	}
}
int ask(int l,int r,int k)
{
	memset(T,0,sizeof(T));c0=c1=0;l--;
	for(;r;r-=r&(-r)) T[1][++c1]=rt[r];
	for(;l;l-=l&(-l)) T[0][++c0]=rt[l];
	return query(1,L,k);
}
int main()
{
	cin>>n>>m;L=n;
	for(int i=1;i<=n;i++) b[i]=a[i]=read();
	for(int i=1;i<=m;i++)
	{
		cin>>opt;q[i].opt=(opt=='Q');
		if(q[i].opt) q[i].l=read(),q[i].r=read(),q[i].k=read();
		  else q[i].p=read(),b[++L]=q[i].t=read();
	}
	sort(b+1,b+L+1);L=unique(b+1,b+L+1)-b-1;
	for(int i=1;i<=n;i++) change(i,1);
	for(int i=1;i<=m;i++)
	{
		if(q[i].opt) printf("%d\n",b[ask(q[i].l,q[i].r,q[i].k)]);
		else change(q[i].p,-1),a[q[i].p]=q[i].t,change(q[i].p,1);
	}
} 

RT,mxqz,为什么此程序在开O2后运行时间(TLE7)远远低于不开O2的时间(AC)