记录编号	277678	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	prefect1999	是否通过	通过
代码语言	C++	运行时间	1.477 s
提交时间	2016-07-06 10:57:57	内存使用	214.54 MiB

/*
树状数组套主席树求解动态区间第k大：
先把数列以及询问读取进来，对所有可能出现的数字进行离散化。
建立树状数组，每个结点存一棵主席树，对于修改操作沿着树状数组上升，把新的新的数ins到途经的结点（还要删除原有的数）即可。
查询操作，先得到查询区间在树状数组中对应的结点集合，然后维护这些结点沿着主席树下降即可。 
注意区分离散化前的值与离散化后的值。 
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxQ = 12000;
const int maxn = 62000;
struct node
{
	int l, r, v;
}T[maxn*300];
int n, m, sz, rank[maxn], A[maxn], C[maxn], len;
pair<int, int> a[maxn];
inline vector<int> sum(int x)
{
	vector<int> ret;
	for (int i = x; i > 0; i -= lowbit(i))
		ret.push_back(C[i]);
	return ret;
}
void ins(int &i, int l, int r, int p, int v)
{
	int m = (l + r) / 2;
	T[++sz] = T[i]; i = sz;
	T[i].v += v;
	if (l == r) return;
	if (p <= m) ins(T[i].l, l, m, p, v);
	else ins(T[i].r, m+1, r, p, v);
}
int kth(int X, int Y, int k)
{
	int l = 1, r = len;
	vector<int> x = sum(X - 1), y = sum(Y);
	while (l < r)
	{
		int m = (l + r) / 2;
		int t = 0;
		for (unsigned i = 0; i < y.size(); ++i)
			t += T[T[y[i]].l].v;
		for (unsigned i = 0; i < x.size(); ++i)
			t -= T[T[x[i]].l].v;
		if (k <= t)
		{
			for (unsigned i = 0; i < x.size(); ++i)
				x[i] = T[x[i]].l;
			for (unsigned i = 0; i < y.size(); ++i)
				y[i] = T[y[i]].l;
			r = m;
		}
		else
		{
			for (unsigned i = 0; i < x.size(); ++i)
				x[i] = T[x[i]].r;
			for (unsigned i = 0; i < y.size(); ++i)
				y[i] = T[y[i]].r;
			l = m + 1;
			k -= t;
		}
	}
	return a[l].first;
}
void init()
{
	sz = 0;
	for (int i = 1; i <= len; ++i)
		a[i].first = A[i], a[i].second = i;
	sort(a + 1, a + len + 1);
	for (int i = 1; i <= len; ++i)
		rank[a[i].second] = i;
}
inline void add(int x, int d, int v = 1)
{
	for (int i = x; i <= n; i += lowbit(i))
		ins(C[i], 1, len, d, v);
}
inline void update(int x, int d)
{
	add(x, A[x], -1);
	add(x, d, 1);
}
struct Query
{
	char tp;
	int x, y, k;
}query[maxQ];
int main()
{
	freopen("dynrank.in", "r", stdin);
	freopen("dynrank.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(C, 0, sizeof(C));
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &A[i]);
		len = n;
		for (int i = 1; i <= m; ++i)
		{
			scanf(" %c %d %d ", &query[i].tp, &query[i].x, &query[i].y);
			if (query[i].tp == 'Q')
				scanf("%d", &query[i].k);
			else
				A[++len] = query[i].y;
		}
		init();
		for (int i = 1; i <= n; ++i)
			add(i, A[i] = rank[i]);
		for (int cnt = n + 1, i = 1; i <= m; ++i)
		{
			if (query[i].tp == 'Q')
			{
				printf("%d\n", kth(query[i].x, query[i].y, query[i].k));
			}
			else
			{
				update(query[i].x, rank[cnt]);
				A[query[i].x] = rank[cnt++];
			}
		}
	}
	return 0;
}