记录编号	454342	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.850 s
提交时间	2017-09-28 19:42:31	内存使用	229.93 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define mem(x) memset((x),0,sizeof((x)))
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
int T,n,m;
int v[50005],num[60005];
int rt[50005],lch[20000005],rch[20000005],sum[20000005];
int A[10005],B[10005],K[10005];
int a,b,L[50],R[50];
bool flag[10005];
int top,cnt,size;
char op[2];
inline void clear(){
	top=cnt=size=0;
	mem(rt),mem(lch),mem(rch),mem(sum),mem(num),mem(flag);
}
inline int lowbit(int x){
	return x&-x;
}
inline void update(int &x,int las,int pos,int w,int l,int r){
	x=++cnt;
	lch[x]=lch[las];
	rch[x]=rch[las];
	sum[x]=sum[las]+w;
	if(l==r)
		return;
	int mid((l+r)>>1);
	if(pos<=mid)
		update(lch[x],lch[las],pos,w,l,mid);
	else
		update(rch[x],rch[las],pos,w,mid+1,r);
}
inline int query(int l,int r,int k){
	if(l==r)
		return l;
	int mid((l+r)>>1),suml(0),sumr(0);
	for(int i=1;i<=a;++i)
		suml+=sum[lch[L[i]]];
	for(int i=1;i<=b;++i)
		sumr+=sum[lch[R[i]]];
	if(k<=sumr-suml){
		for(int i=1;i<=a;++i)
			L[i]=lch[L[i]];
		for(int i=1;i<=b;++i)
			R[i]=lch[R[i]];
		return query(l,mid,k);
	}
	else{
		for(int i=1;i<=a;++i)
			L[i]=rch[L[i]];
		for(int i=1;i<=b;++i)
			R[i]=rch[R[i]];
		return query(mid+1,r,k-(sumr-suml));
	}
}
int main(){
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	T=read();
	while(T--){
		clear();
		n=read(),m=read();
		for(int i=1;i<=n;++i)
			v[i]=read(),num[++top]=v[i];
		for(int i=1;i<=m;++i){
			scanf("%s",op);
			if(op[0]=='Q'){
				flag[i]=1;
				A[i]=read();
				B[i]=read();
				K[i]=read();
			}
			else{
				A[i]=read();
				B[i]=read();
				num[++top]=B[i];
			}
		}
		sort(num+1,num+top+1);
		size=unique(num+1,num+top+1)-num-1;
		for(int i=1;i<=n;++i){
			v[i]=lower_bound(num+1,num+size+1,v[i])-num;
			for(int j=i;j<=n;j+=lowbit(j))
				update(rt[j],rt[j],v[i],1,1,size);
		}
		for(int i=1;i<=m;++i){
			if(flag[i]){
				a=b=0;
				--A[i];
				for(int j=A[i];j>0;j-=lowbit(j))
					L[++a]=rt[j];
				for(int j=B[i];j>0;j-=lowbit(j))
					R[++b]=rt[j];
				printf("%d\n",num[query(1,size,K[i])]);
			}
			else{
				int tmp(v[A[i]]);
				for(int j=A[i];j<=n;j+=lowbit(j))
					update(rt[j],rt[j],tmp,-1,1,size);
				tmp=lower_bound(num+1,num+size+1,B[i])-num;
				v[A[i]]=tmp;
				for(int j=A[i];j<=n;j+=lowbit(j))
					update(rt[j],rt[j],tmp,1,1,size);
			}
		}
	}
}