ZOJ上面这题内存限制太严格，裸的树套树主席树搞法过不去，BZOJ上面这个放的比较松，可以过。
其实就是利用树状数组维护n颗主席树，然后利用前缀和性质求解第k大。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#include <sstream>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
#define MP make_pair
#define PB push_back
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = INT_MAX / 3;
const double eps = 1e-8;
const LL LINF = 1e17;
const double DINF = 1e60;
const int maxn = 5e4 + 10;
const int maxm = maxn * 67;
const int maxq = 1e4 + 10;
struct Query {
char cmd;
int l, r, k;
Query(char cmd = 0, int l = 0, int r = 0, int k = 0):
cmd(cmd), l(l), r(r), k(k) {}
};
int sumv[maxm], lc[maxm], rc[maxm], cnt, C[maxn];
int n, m, num[maxn + maxq], numcnt, a[maxn];
Query ask[maxq];
int lowbit(int x) {
return x & (-x);
}
void init() {
cnt = numcnt = 0;
memset(C, 0, sizeof(C));
}
void build(int rt, int l, int r) {
sumv[rt] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
lc[rt] = cnt++; rc[rt] = cnt++;
build(lc[rt], l, mid);
build(rc[rt], mid + 1, r);
}
int update(int prt, int pos, int Val) {
int nrt = cnt++, ret = nrt;
sumv[nrt] = sumv[prt] + Val;
int l = 0, r = numcnt - 1;
while(l < r) {
int mid = (l + r) >> 1;
if(pos <= mid) {
lc[nrt] = cnt++; rc[nrt] = rc[prt];
sumv[lc[nrt]] = sumv[lc[prt]] + Val;
nrt = lc[nrt]; prt = lc[prt];
r = mid;
}
else {
rc[nrt] = cnt++; lc[nrt] = lc[prt];
sumv[rc[nrt]] = sumv[rc[prt]] + Val;
nrt = rc[nrt]; prt = rc[prt];
l = mid + 1;
}
}
return ret;
}
void gao(int tid, int pos, int Val) {
while(tid <= n) {
int ret = update(C[tid], pos, Val);
C[tid] = ret;
tid += lowbit(tid);
}
}
int lrt[maxn], rrt[maxn];
int query(int ql, int qr, int k) {
int lcnt = 0, rcnt = 0;
ql--;
while(ql > 0) {
lrt[lcnt++] = C[ql];
ql -= lowbit(ql);
}
while(qr > 0) {
rrt[rcnt++] = C[qr];
qr -= lowbit(qr);
}
int l = 0, r = numcnt - 1;
while(l < r) {
int mid = (l + r) >> 1, lsum = 0, rsum = 0;
for(int i = 0; i < lcnt; i++) lsum += sumv[lc[lrt[i]]];
for(int i = 0; i < rcnt; i++) rsum += sumv[lc[rrt[i]]];
if(rsum - lsum >= k) {
r = mid;
for(int i = 0; i < lcnt; i++) lrt[i] = lc[lrt[i]];
for(int i = 0; i < rcnt; i++) rrt[i] = lc[rrt[i]];
}
else {
l = mid + 1; k -= (rsum - lsum);
for(int i = 0; i < lcnt; i++) lrt[i] = rc[lrt[i]];
for(int i = 0; i < rcnt; i++) rrt[i] = rc[rrt[i]];
}
}
return l;
}
int getid(int Val) {
return lower_bound(num, num + numcnt, Val) - num;
}
int main() {
init();
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
num[numcnt++] = a[i];
}
char cmd[5];
int l, r, k;
for(int i = 1; i <= m; i++) {
scanf("%s", cmd);
if(cmd[0] == 'Q') {
scanf("%d%d%d", &l, &r, &k);
ask[i] = Query(cmd[0], l, r, k);
}
else {
scanf("%d%d", &l, &k);
ask[i] = Query(cmd[0], l, 0, k);
num[numcnt++] = k;
}
}
sort(num, num + numcnt);
numcnt = unique(num, num + numcnt) - num;
build(0, 0, numcnt - 1);
for(int i = 1; i <= n; i++) {
gao(i, getid(a[i]), 1);
}
for(int i = 1; i <= m; i++) {
if(ask[i].cmd == 'Q') printf("%d
", num[query(ask[i].l, ask[i].r, ask[i].k)]);
else {
int prev = getid(a[ask[i].l]), now = getid(ask[i].k);
a[ask[i].l] = ask[i].k;
gao(ask[i].l , prev, -1); gao(ask[i].l, now, 1);
}
}
return 0;
}