记录编号	370504	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	1.143 s
提交时间	2017-02-13 21:16:25	内存使用	42.28 MiB

//BZOJ1901
//by Cydiater
//2017.2.13
#include <iostream>
#include <map>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <string>
#include <ctime>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <set>
#include <vector>
#include <complex>
using namespace std;
#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define FILE		"dynrank"
const int MAXN=5e5+5;
const int oo=1e9+1;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,M,ans[MAXN],cnt=0,arr[MAXN],tmp[MAXN];
struct Mix{
	int op,x,y,k,id,cnt;
}m[MAXN],m1[MAXN],m2[MAXN];
namespace BIT{
	int c[MAXN];
	inline int lowbit(int i){return i&(-i);}
	inline void ADD(int pos,int val){
		for(int i=pos;i<=N;i+=lowbit(i))c[i]+=val;
	}
	inline int SUM(int pos){
		int ans=0;
		for(int i=pos;i>=1;i-=lowbit(i))ans+=c[i];
		return ans;
	}
}
namespace solution{
	void Prepare(){
		up(i,1,N){
			m[i].op=1;m[i].x=read();m[i].y=i;
			arr[i]=m[i].x;
		}
		up(i,1,M){
			char s[5];
			scanf("%s",s);
			if(s[0]=='Q'){
				m[i+N].op=2;m[i+N].x=read();m[i+N].y=read();m[i+N].k=read();m[i+N].cnt=0;m[i+N].id=++cnt;
			}else{
				M++;
				m[i+N].op=3;;m[i+N].y=read();m[i+N].x=arr[m[i+N].y];
				i++;
				m[i+N].op=1;m[i+N].x=read();m[i+N].y=m[i+N-1].y;
				arr[m[i+N].y]=m[i+N].x;
			}
		}
	}
	void Divide(int head,int tail,int L,int R){
		if(head>tail)return;
		//cout<<head<<' '<<tail<<' '<<L<<' '<<R<<endl;
		//up(i,head,tail)cout<<m[i].op<<' '<<m[i].x<<' '<<m[i].y<<' '<<m[i].cnt<<endl;
		//cout<<endl;
		if(L==R){
			up(i,head,tail)if(m[i].op==2)ans[m[i].id]=L;
			return;
		}
		int mid=(L+R)>>1;
		up(i,head,tail){
			if(m[i].op==1&&m[i].x<=mid)BIT::ADD(m[i].y,1);
			if(m[i].op==3&&m[i].x<=mid)BIT::ADD(m[i].y,-1);
			if(m[i].op==2)tmp[i]=BIT::SUM(m[i].y)-BIT::SUM(m[i].x-1);
		}
		up(i,head,tail){
			if(m[i].op==1&&m[i].x<=mid)BIT::ADD(m[i].y,-1);
			if(m[i].op==3&&m[i].x<=mid)BIT::ADD(m[i].y,1);
		}
		int t1=0,t2=0;
		up(i,head,tail){
			if(m[i].op==2){
				if(m[i].cnt+tmp[i]<m[i].k){
					m[i].cnt+=tmp[i];
					m2[++t2]=m[i];
				}
				else	m1[++t1]=m[i];
			}else{
				if(m[i].x<=mid)	m1[++t1]=m[i];
				else		m2[++t2]=m[i];
			}
		}
		up(i,head,head+t1-1)m[i]=m1[i-head+1];
		up(i,head+t1,tail)m[i]=m2[i-head-t1+1];
		Divide(head,head+t1-1,L,mid);
		Divide(head+t1,tail,mid+1,R);
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	//freopen("input.in","r",stdin);
	//freopen("out1.out","w",stdout);
	using namespace solution;
	int T=read();
	while(scanf("%d %d",&N,&M)!=EOF){
		cnt=0;
		Prepare();
		Divide(1,N+M,0,oo);
		up(i,1,cnt)printf("%d\n",ans[i]);
	}
	return 0;
}