记录编号	266894	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.006 s
提交时间	2016-06-10 08:44:17	内存使用	14.05 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=200010;
int T,n,Q,cntQ;
int num[maxn],ans[maxn],bit[maxn];
char op[10];
struct Node{
	int x,y,k,id,tp;
}a[maxn],t1[maxn],t2[maxn];
//tp==1 add; tp==2 del; tp==3 query;

void Add(int x,int d){
	while(x<=n){
		bit[x]+=d;
		x+=x&(-x);
	}
}

int Query(int x){
	int ret=0;
	while(x){
		ret+=bit[x];
		x-=x&(-x);
	}
	return ret;
}

void Solve(int h,int t,int l,int r){
	if(l==r){
		for(int i=h;i<=t;i++)
			if(a[i].tp==3)ans[a[i].id]=l;
		return;
	}
	if(h>t)return;
	int p1=0,p2=0,d;
	for(int i=h;i<=t;i++){
		if(a[i].tp==3){
			d=Query(a[i].y)-Query(a[i].x-1);
			if(d>=a[i].k)t1[++p1]=a[i];
			else{
				a[i].k-=d;
				t2[++p2]=a[i];
			}
		}
		else if(a[i].k<=l+r>>1){
			if(a[i].tp==1)Add(a[i].x,1);
			if(a[i].tp==2)Add(a[i].x,-1);
			t1[++p1]=a[i];
		}
		else t2[++p2]=a[i];
	}
	for(int i=h;i<=t;i++){
		if(a[i].k<=l+r>>1){
			if(a[i].tp==1)Add(a[i].x,-1);
			if(a[i].tp==2)Add(a[i].x,1);
		}
	}
	for(int i=1;i<=p1;i++)a[h+i-1]=t1[i];
	for(int i=1;i<=p2;i++)a[h+i+p1-1]=t2[i];
	Solve(h,h+p1-1,l,l+r>>1);
	Solve(h+p1,t,(l+r>>1)+1,r);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&Q);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i].k);
			a[i].x=i;a[i].tp=1;
			num[i]=a[i].k;
		}
		cntQ=0;
		int x,y,k;
		while(Q--){
			scanf("%s",op);
			if(op[0]=='Q'){
				scanf("%d%d%d",&x,&y,&k);
				a[++n].id=++cntQ;a[n].tp=3;
				a[n].x=x;a[n].y=y;a[n].k=k;
			}
			else{
				scanf("%d%d",&x,&k);
				a[++n].tp=2;a[n].x=x;a[n].k=num[x];
				a[++n].tp=1;a[n].x=x;a[n].k=k;num[x]=k;
			}
		}
		Solve(1,n,1,1000000000);
		for(int i=1;i<=cntQ;i++)
			printf("%d\n",ans[i]);			
	}
	return 0;	
}