记录编号	100315	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Suke	是否通过	通过
代码语言	C++	运行时间	1.312 s
提交时间	2014-05-05 11:52:07	内存使用	116.22 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 50010
struct segment{
	int l,r,sum;
} t[maxn*200];
int cnt,tot,n,m,N,M;
int data[maxn],hash[maxn*2],root[maxn];
int L[2000],R[2000];
char opt[maxn][2];
int X[maxn],Y[maxn],Z[maxn];
inline int lowbit(int x){return x&(-x);}
void build(int &x,int l,int r){
	t[x=++tot].sum=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(t[x].l,l,mid);
	build(t[x].r,mid+1,r);
}
void update(int last,int y,int l,int r,int &x,int flag){
	t[x=++tot].sum=t[last].sum+flag;
	t[x].l=t[last].l;t[x].r=t[last].r;
	if(l==r) return;
    int mid=(l+r)>>1;
    if(y<=mid) update(t[last].l,y,l,mid,t[x].l,flag);
    else update(t[last].r,y,mid+1,r,t[x].r,flag);
}

int ask(int l,int r,int k){
	if(l==r) return l;
	int now=0,i;
	for(i=1;i<=N;++i) now-=t[t[L[i]].l].sum;
	for(i=1;i<=M;++i) now+=t[t[R[i]].l].sum;
	int mid=(l+r)/2;
	if(k<=now){
		for(i=1;i<=N;++i) L[i]=t[L[i]].l;
		for(i=1;i<=M;++i) R[i]=t[R[i]].l;
		return ask(l,mid,k);
	}
	else{
		for(i=1;i<=N;++i) L[i]=t[L[i]].r;
		for(i=1;i<=M;++i) R[i]=t[R[i]].r;
		return ask(mid+1,r,k-now);
	}
}
int bit_ask(int l,int r,int k){
	N=0;M=0;
	for(;l;l-=lowbit(l)) L[++N]=root[l];
	for(;r;r-=lowbit(r)) R[++M]=root[r];
	return ask(1,cnt,k);
} 
void bit_update(int x,int y,int flag){
	for(;x<=n;x+=lowbit(x))
	 update(root[x],y,1,cnt,root[x],flag);
}
int main(){
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
int sk;
cin>>sk;
while(sk--){
	scanf("%d%d",&n,&m);
	cnt=0;tot=0;
	memset(root,0,sizeof(root));//!!!!
	int i;
	for(i=1;i<=n;++i) scanf("%d",data+i),hash[++cnt]=data[i];
	for(i=1;i<=m;++i){
		scanf("%s%d%d",opt[i],X+i,Y+i);
		if(opt[i][0]=='Q') scanf("%d",Z+i);
		else hash[++cnt]=Y[i];
	}
	sort(hash+1,hash+cnt+1);
	cnt=unique(hash+1,hash+cnt+1)-hash-1;
	build(root[0],1,cnt);
	for(i=1;i<=n;++i){
		data[i]=lower_bound(hash+1,hash+cnt+1,data[i])-hash;
	    bit_update(i,data[i],1);	
	}
	for(i=1;i<=m;++i){
		if(opt[i][0]=='Q')
			printf("%d\n",hash[bit_ask(X[i]-1,Y[i],Z[i])]);
        else{
        	bit_update(X[i],data[X[i]],-1);
        	data[X[i]]=lower_bound(hash+1,hash+cnt+1,Y[i])-hash;
        	bit_update(X[i],data[X[i]],1);
        }
	}
}
}