记录编号	189260	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	11.695 s
提交时间	2015-09-26 19:54:59	内存使用	1.02 MiB

#include<cstdio>
#include<set>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=300;
int T,N,M,S,best,ma=0;
class miku
{
    public:
	int s[SIZEN];
	int a[SIZEN];//排好的序列
	int n;
	void clear(){n=0;memset(s,0,sizeof(s));memset(a,0,sizeof(a));}
	void Sort()
	{
		for(int i=1;i<=n;i++) a[i]=s[i];
		sort(a+1,a+n+1);
	}
	miku split(int x,bool type)//1是从前到后，0是从后到前
	{
		int st,ed;
		if(type) st=1,ed=x;
		else st=x,ed=n;
		miku re;
		re.clear();
		for(int i=st;i<=ed;i++) re.s[++re.n]=s[i];
		re.Sort();
		return re;
	}
	void print()
	{
		cout<<n<<endl;
		for(int i=1;i<=n;i++)
			cout<<s[i]<<" ";
		cout<<endl;
	}
	int sum(int x)
	{
		int l=1,r=n;
		if(r==1) 
		{
			if(a[1]<=x) return 1;
			else return 0;
		}
		while(l<r)
		{
			int mid=(l+r)/2;
			if(a[mid]<x) l=mid+1;
			else r=mid;
		}
		while(a[r]==x) r++;
		while(a[r]>x||a[r]==0&&r>0) r--;
		return r;
	}
};
miku P[SIZEN+10];
void check_P()
{
	for(int i=1;i<=S;i++)
	P[i].print();
}
int get(int &x)
{
	int re=0;
	while(x>P[re].n){x-=P[re].n;re++;}
	return re;
}
void change()
{
	int x,t;
	scanf("%d%d",&x,&t);
	if(t>ma) ma=t;
	int m=get(x);
	P[m].s[x]=t;
	P[m].Sort();
}
void sum()
{
	int l,r,k;
	scanf("%d%d%d",&l,&r,&k);
	int teml=get(l),temr=get(r);
	miku a,b;
	a.clear();b.clear();
	if(teml==temr)
	{
		for(int i=l;i<=r;i++)
		a.s[++a.n]=P[teml].s[i];
	}
	else
	{
	    a=P[teml].split(l,0);
	    b=P[temr].split(r,1);
	}
	int le=1,ri=ma;
	while(le<ri)
	{
		int mid=(ri+le)/2;
		int tem=0;
		for(int i=teml+1;i<=temr-1;i++) tem+=P[i].sum(mid);
		tem+=a.sum(mid);//cout<<"a.sum:"<<a.sum(mid)<<endl;
		tem+=b.sum(mid);//cout<<"b.sum:"<<b.sum(mid)<<endl;
		if(tem>=k) ri=mid;
		else le=mid+1;
		//a.print();b.print();
		//cout<<mid<<" "<<tem<<endl;
		//cout<<endl;
	}
	printf("%d\n",ri);
}
void read()
{
	for(int i=0;i<=S;i++) P[i].clear();
	scanf("%d%d",&N,&M);
	best=sqrt(N+0.0);ma=0;
	int a;S=1;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a);
		P[S].s[++P[S].n]=a;ma=max(a,ma);
		if(P[S].n>best) S++;
	}
	for(int i=0;i<=S;i++)
		P[i].Sort();
}
void work()
{
	char ch;
	for(int i=1;i<=M;i++)
	{
		scanf("%c",&ch);
		while(ch!='Q'&&ch!='C') scanf("%c",&ch);
		if(ch=='Q') sum();
		else if(ch=='C') change();
		//else cout<<"error"<<endl;
	}
}
int main()
{
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++){read();work();}
	return 0;
}