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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=50010;
void modifyc(int,int);
void queryc(int,int);
void add(int,int,int&);
void query(int,int);
int sm[maxn<<8],lc[maxn<<8],rc[maxn<<8],root[maxn],cnt,ra[maxn],rb[maxn],cnta,cntb;
int T,n,m,a[maxn],l,r,x,p,d,k,ans;
char c;
int main(){
#define MINE
#ifdef MINE
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		memset(root,0,sizeof(root));
		memset(a,0,sizeof(a));
		cnt=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			modifyc(i,x);
		}
		while(m--){
			scanf(" %c",&c);
			if(c=='C'){
				scanf("%d%d",&x,&d);
				modifyc(x,d);
			}
			else{
				scanf("%d%d%d",&l,&r,&k);
				queryc(l,r);
				printf("%d\n",ans);
			}
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void modifyc(int x,int k){
	if(a[x]){
		d=-1;
		p=a[x];
		for(int i=x;i<=n;i+=lowbit(i))add(1,1000000000,root[i]);
	}
	d=1;
	p=a[x]=k;
	while(x<=n){
		add(1,1000000000,root[x]);
		x+=lowbit(x);
	}
}
void queryc(int l,int r){
	cnta=cntb=0;
	l--;
	while(l){
		ra[++cnta]=root[l];
		l-=lowbit(l);
	}
	while(r){
		rb[++cntb]=root[r];
		r-=lowbit(r);
	}
	query(1,1000000000);
}
void add(int l,int r,int &rt){
	if(!rt){
		rt=++cnt;
		sm[rt]=lc[rt]=rc[rt]=0;
	}
	sm[rt]+=d;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(p<=mid)add(l,mid,lc[rt]);
	else add(mid+1,r,rc[rt]);
}
void query(int l,int r){
	if(l==r){
		ans=l;
		return;
	}
	int mid=(l+r)>>1,tmp=0;
	for(int i=1;i<=cnta;i++)tmp-=sm[lc[ra[i]]];
	for(int i=1;i<=cntb;i++)tmp+=sm[lc[rb[i]]];
	if(k<=tmp){
		for(int i=1;i<=cnta;i++)ra[i]=lc[ra[i]];
		for(int i=1;i<=cntb;i++)rb[i]=lc[rb[i]];
		query(l,mid);
	}
	else{
		k-=tmp;
		for(int i=1;i<=cnta;i++)ra[i]=rc[ra[i]];
		for(int i=1;i<=cntb;i++)rb[i]=rc[rb[i]];
		query(mid+1,r);
	}
}