记录编号	455052	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	2.935 s
提交时间	2017-10-01 06:06:04	内存使用	0.69 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#define N 50005
#define inf 1000000000
using namespace std;
int n,m,D,tot,a[N];
namespace chairtree
{
	struct tree
	{
		tree* lc;tree* rc;
		int sum;
		tree(){lc=rc=NULL;sum=0;}
		inline void updata(){sum=lc->sum+rc->sum;}
	}*null=new tree(),*root[N];
	vector<tree*> v[3];
	tree* newtree()
	{
		tree* o=new tree();
		o->lc=o->rc=null;
		o->sum=0;
		return o;
	}
	void getins(int id,int x)
	{
		v[id].clear();
		while(x<=n){v[id].push_back(root[x]);x+=x&(-x);}
	}
	void getq(int id,int x)
	{
		v[id].clear();
		while(x>0){v[id].push_back(root[x]);x-=x&(-x);}
	}
	void insert(vector<tree*> v,int l,int r,int k,int h)
	{
		int len=v.size(),mid;
		while(l<r)
		{
			mid=l+r>>1;
			for(int i=0;i<len;i++)if(v[i]!=null)v[i]->sum+=h;
			if(k<=mid)
			{
				for(int i=0;i<len;v[i]=v[i]->lc,i++)
					if(v[i]->lc==null)v[i]->lc=newtree();
				r=mid;
			}
			else
			{
				for(int i=0;i<len;v[i]=v[i]->rc,i++)
					if(v[i]->rc==null)v[i]->rc=newtree();
				l=mid+1;
			}
		}
		for(int i=0;i<len;i++)
		{
			if(v[i]==null)v[i]=newtree();
			v[i]->sum+=h;
		}
	}
	int q(int l,int r,int a,int b,int k)
	{
		getq(1,a-1);getq(2,b);
		int mid,cmp,len1=v[1].size(),len2=v[2].size();
		while(l<r)
		{
			cmp=0;mid=l+r>>1;//printf("%d %d\n",mid,cmp);
			for(int i=0;i<len1;i++)if(v[1][i]!=null)cmp-=v[1][i]->lc->sum;
			for(int i=0;i<len2;i++)if(v[2][i]!=null)cmp+=v[2][i]->lc->sum;

			if(cmp>=k)
			{
				for(int i=0;i<len1;i++)v[1][i]=v[1][i]->lc;
				for(int i=0;i<len2;i++)v[2][i]=v[2][i]->lc;
				r=mid;
			}
			else
			{	
				for(int i=0;i<len1;i++)v[1][i]=v[1][i]->rc;
				for(int i=0;i<len2;i++)v[2][i]=v[2][i]->rc;
				l=mid+1;k-=cmp;
			}
		}
		return r;
	}
	void change(int l,int k)
	{
		getins(1,l);
		insert(v[1],1,inf,a[l],-1);
		insert(v[1],1,inf,k,1);
		a[l]=k;
	}
}
using namespace chairtree;
int main()
{	
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	scanf("%d",&D);null->lc=null->rc=null;
	while(D--)
	{
		scanf("%d%d",&n,&m);int l,r,k;char s[2];
		for(int i=1;i<=n;i++)root[i]=newtree();
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),getins(1,i),insert(v[1],1,inf,a[i],1);
		while(m--)
		{
			scanf("%s",s);
			if(s[0]=='Q'){scanf("%d%d%d",&l,&r,&k);printf("%d\n",q(1,inf,l,r,k));}
			else{scanf("%d%d",&l,&k);change(l,k);}
		}
	}
}