记录编号	140784	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.122 s
提交时间	2014-11-25 13:12:14	内存使用	115.72 MiB

#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline void getd(int &x){
	char c = getchar();
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
inline int lowbit(int x){return x & -x;}
const int maxn = 50002, maxm = 10001;
int N, M;
int index[maxn + maxm], Cnt, A[maxn], B[maxn + maxm];
inline int getind(int x){return lower_bound(index, index + Cnt, x) - index;}
bool QC[maxm] = {0};//0:Q 1:C
int Oi[maxm], Oj[maxm], K[maxm];

struct SegT{
	int sum;
	SegT *son1, *son2;
	void add(int, int, int);
	void init(int);
}Pool[10000000], *Arr[maxn];
int Pcnt = 0;
void SegT::init(int len){
	sum = 0;
	if(len == 1)return;
	son1 = Pool + Pcnt++;
	son1 -> init(len >> 1);
	son2 = Pool + Pcnt++;
	son2 -> init(len - (len >> 1));
}
void SegT::add(int ind, int d, int len){
	sum += d;
	if(len == 1) return;
	int mid = len >> 1;
	if(mid > ind){
		Pool[Pcnt] = *son1;
		son1 = Pool + Pcnt++;
		son1 -> add(ind, d, mid);
	}
	else{
		Pool[Pcnt] = *son2;
		son2 = Pool + Pcnt++;
		son2 -> add(ind - mid, d, len - mid);
	}
}
//Fenwick
inline void add(int L, int x, int d){//线段树中的x位置
	int i = L;
	while(i <= N){
		Arr[i] -> add(x, d, Cnt);
		i += lowbit(i);
	}
}

inline void init(){
	int i, j, bcnt = 0, ch;
	getd(N), getd(M);
	for(i = 1;i <= N;++i)
		getd(A[i]), B[bcnt++] = A[i];
	for(i = 0;i < M;++i){
		while(!isalpha(ch = getchar()));
		if(ch == 'Q')
			QC[i] = 0, getd(Oi[i]), getd(Oj[i]), getd(K[i]);
		else
			QC[i] = 1, getd(Oi[i]), getd(Oj[i]), B[bcnt++] = Oj[i];
	}
	//离散化
	sort(B, B + bcnt);
	Cnt = 1;
	index[0] = B[0];
	for(i = 1;i < bcnt;++i) if(B[i] != index[Cnt-1])
		index[Cnt++] = B[i];
	
	Pcnt = 1;
	(Arr[0] = Pool) -> init(Cnt);
	for(i = 1;i <= N;++i){
		Arr[i] = Pool + Pcnt++;
		*Arr[i] = *Arr[0];
	}
	for(i = 1;i <= N;++i){
		j = getind(A[i]);
		add(i, j, 1);
	}
}

inline void Query(int x){
	SegT *iter1[20], *iter2[20];
	int n1 = 0, n2 = 0;
	int i, s1, s2, L = Oi[x], R = Oj[x], k = K[x], l = 0, r = Cnt;
	i = L - 1;
	while(i){
		iter1[n1++] = Arr[i];
		i ^= lowbit(i);
	}
	i = R;
	while(i){
		iter2[n2++] = Arr[i];
		i ^= lowbit(i);
	}
	while(1){
		if(r - l == 1)break;
		s1 = s2 = 0;
		for(i = 0;i < n1;++i)s1 += iter1[i]->son1->sum;
		for(i = 0;i < n2;++i)s2 += iter2[i]->son1->sum;
		if(s2 - s1 >= k){
			r = (l + r) >> 1;
			for(i = 0;i < n1;++i)iter1[i] = iter1[i]->son1;
			for(i = 0;i < n2;++i)iter2[i] = iter2[i]->son1;
		}
		else {
			k -= (s2 - s1);
			l = (l + r) >> 1;
			for(i = 0;i < n1;++i)iter1[i] = iter1[i]->son2;
			for(i = 0;i < n2;++i)iter2[i] = iter2[i]->son2;
		}
	}
	printf("%d\n", index[l]);
}

inline void change(int i){
	int i1 = getind(A[Oi[i]]), i2 = getind(Oj[i]);
	A[Oi[i]] = Oj[i];
	add(Oi[i], i1, -1);
	add(Oi[i], i2, 1);
}

inline void work(){
	init();
	int i;
	for(i = 0;i < M;++i){
		if(QC[i]) change(i);
		else Query(i);
	}
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("dynrank.in", "r", stdin);
	freopen("dynrank.out", "w", stdout);
	#endif
	
	int T;
	getd(T);
	while(T--)
		work();
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}