记录编号	155738	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	1.090 s
提交时间	2015-03-30 09:53:25	内存使用	86.62 MiB

#include<iostream>
#include<cstdio>
using namespace std;
#define lowbit(x) x&-x
char ch;
int n,m,i,T,num,qnum,zj1,zj2,zj3,MAX;

struct www{int typ,x,y,w,ret;}Al[31][70100],Ar[31][70100];
int z[50010]={0},ans[50010]={0};

int tree[50010]={0};
inline void add_(int x,int c)
{for(;x<=n;x+=lowbit(x))tree[x]+=c;}
inline int get_(int u,int v)
{
	int Sum=0;
	for(;u;u-=lowbit(u))Sum+=tree[u];
	for(Sum=-Sum;v;v-=lowbit(v))Sum+=tree[v];
	return Sum;
}

inline void cdq(int dep,www *work,int L,int R)
{
	if(!work[0].w)return;
	int mid=(L+R)>>1,h,lnum=0,rnum=0;
	www *lw=Al[dep],*rw=Ar[dep];
	
	for(h=1;h<=work[0].w;h++)
	if(work[h].typ!=2)
		if(work[h].w>mid)rw[++rnum]=work[h];
		else
		{
			lw[++lnum]=work[h];
			if(work[h].typ==1)add_(work[h].x,1);
			else add_(work[h].x,-1);
		}
	else
	{
		zj1=get_(work[h].x-1,work[h].y);
		if(zj1<work[h].w)work[h].w-=zj1,rw[++rnum]=work[h];
		else ans[work[h].ret]=mid,lw[++lnum]=work[h];
	}
	for(h=1;h<=work[0].w;h++)if(work[h].w<=mid)
	if(work[h].typ==1)add_(work[h].x,-1);
	else if(work[h].typ==3)add_(work[h].x,1);
	
	if(L==R)return;
	lw[0].w=lnum,rw[0].w=rnum;
	cdq(dep+1,lw,L,mid);cdq(dep+1,rw,mid+1,R);
}
int main()
{
	//freopen("a.txt","r",stdin);
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(MAX=0,num=0,i=1;i<=n;i++)
		{
			scanf("%d",z+i);
			Ar[0][++num]=(www){1,i,0,z[i],0};
			if(MAX<z[i])MAX=z[i];
		}
		for(qnum=0,i=1;i<=m;i++)
		{
			while((ch=getchar())<'A'||ch>'Z');
			if(ch=='Q')
			{
				scanf("%d%d%d",&zj1,&zj2,&zj3);
				Ar[0][++num]=(www){2,zj1,zj2,zj3,++qnum};
			}
			else
			{
				scanf("%d%d",&zj1,&zj2);
				Ar[0][++num]=(www){3,zj1,0,z[zj1],0};
				Ar[0][++num]=(www){1,zj1,0,zj2,0};
				z[zj1]=zj2;if(MAX<zj2)MAX=zj2;
			}
		}
		Ar[0][0].w=num;
		cdq(1,Ar[0],1,MAX);
		for(i=1;i<=qnum;i++)
		printf("%d\n",ans[i]);
	}
	return 0;
}