记录编号	157775	评测结果	TTTTTTAATT
题目名称	动态排名系统	最终得分	20
用户昵称	HouJikan	是否通过	未通过
代码语言	C++	运行时间	48.006 s
提交时间	2015-04-10 10:08:54	内存使用	21.68 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct Options{
	int x,y,k,type,No;
	int cur;
	Options(){cur=0;}
};
///==============var declaration=================
const int MAXN=200050;
int T,n,m,tot=0,buf=0,Sm,ans_cnt;
int A[MAXN],h[MAXN],rev[MAXN*2],Answer[MAXN];
int Bit[MAXN*3],rem[MAXN*2];
Options opt[MAXN],q1[MAXN],q2[MAXN];
map <int,int> mp;
///==============function declaration============
void Solve(int l,int r,int L,int R);
inline int lowbit(int x){return x&-x;}
void Add(int x,int k){for(;x<=Sm;x+=lowbit(x)) Bit[x]+=k;}
inline int Query(int x){int res;for(res=0;x>0;x-=lowbit(x)) res+=Bit[x];return res;}
inline int read();
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("dynrank.in","r",stdin);
   freopen("dynrank.out","w",stdout);
	//endif
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);tot=buf=Sm=ans_cnt=0;mp.clear();
		memset(opt,0,sizeof(opt));memset(q1,0,sizeof(q1));
		memset(q2,0,sizeof(q2));
		for(int i=1;i<=n;i++){
			int v=read();tot++;
			A[i]=v;
			opt[tot].type=1;opt[tot].x=i;
			opt[tot].y=v;h[++buf]=v;
		}
		for(int i=1;i<=m;i++){
			char ch;
			do{
				ch=getchar();
			}while (ch!='Q'&&ch!='C');
			if (ch=='Q'){
				tot++;ans_cnt++;
				opt[tot].x=read();opt[tot].y=read();opt[tot].k=read();
				opt[tot].type=3;opt[tot].No=ans_cnt;
			}
			else if (ch=='C'){
				int x=read(),y=read();h[++buf]=y;
				tot++;
				opt[tot].x=x;opt[tot].y=y;opt[tot].k=1;opt[tot].type=2;
				tot++;
				opt[tot].x=x;opt[tot].y=A[x];opt[tot].k=-1;opt[tot].type=2;
				A[x]=y;
			}
			else printf("Init Err!\n");
		}
		sort(h+1,h+1+buf);Sm=unique(h+1,h+1+buf)-h-1;
		for(int i=1;i<=Sm;i++){
			mp[h[i]]=i;
			rev[i]=h[i];
		}
		for(int i=1;i<=tot;i++){
			if (opt[i].type!=3)
				opt[i].y=mp[opt[i].y];
		}
		Solve(1,tot,1,Sm);
		for(int i=1;i<=ans_cnt;i++)
			printf("%d\n",rev[Answer[i]]);
	}
   return 0;
}
///================fuction code====================
void Solve(int l,int r,int L,int R){///Boundary of opts is [l,r]
 	int M=(L+R)>>1;
	if (l>r) return;
	if (L==R){
		for(int i=l;i<=r;i++)
			if (opt[i].type==3)
				Answer[opt[i].No]=L;
		return;
	}
	for(int i=l;i<=r;i++){
		if (opt[i].type==1){///Insert x is position,y is value
			if (opt[i].y<=M)
				Add(opt[i].x,1);
		}
		else if (opt[i].type==2){///Change x is positon, y is value,k is old value
			if (opt[i].y<=M)
				Add(opt[i].x,opt[i].k);
		}
		else if (opt[i].type==3)
			rem[i]=Query(opt[i].y)-Query(opt[i].x-1);
	}
	int t1=0,t2=0;
	for(int i=l;i<=r;i++){
		if (opt[i].type==1||opt[i].type==2)
			if (opt[i].y<=M)
				q1[++t1]=opt[i];
			else
				q2[++t2]=opt[i];
		else if (opt[i].type==3){
			if (rem[i]+opt[i].cur>=opt[i].k)
				q1[++t1]=opt[i];
			else{
				opt[i].cur+=rem[i];
				q2[++t2]=opt[i];
			}
		}
	}
	for(int i=l;i<=r;i++){
		if (opt[i].type==1){///Insert x is position,y is value
			if (opt[i].y<=M)
				Add(opt[i].x,-1);
		}
		else if (opt[i].type==2){///Change x is positon, y is value,k is old value
			if (opt[i].y<=M)
				Add(opt[i].x,-opt[i].k);
		}
	}
	for(int i=1;i<=t1;i++)
		opt[l+i-1]=q1[i];
	for(int i=1;i<=t2;i++)
		opt[l+t1+i-1]=q2[i];
	Solve(l,l+t1-1,L,M);
	Solve(l+t1,r,M+1,R);
}
inline int read(){
  int res=-1;
  char c;
  while (c=getchar())
  {
    while (c=='\n') c=getchar();
    if (!(c>='0'&&c<='9'))break;      
    if (res==-1) res=0;
    res=res*10+c-'0';
  }
  return res;
}