在沒有修改操作時，應用劃分樹可以在O(MlogN)時間內解決查找區(qū)間第K小的問題，但是在引入修改（將原序列中的某個值改為另一個值）之后，劃分樹就不行了。
這時，需要數據結構聯(lián)合的思想。
可以觀察一下：
（1）區(qū)間操作：使用線段樹；
（2）修改值（其實是先刪除再插入）和找第K小：使用平衡樹；
現在這兩種操作都有，應該使用
線段樹+平衡樹！
準確來說是線段樹套平衡樹，即對原序列建立一棵線段樹，其中的每個結點內套一棵對該結點管轄區(qū)間內的平衡樹。
<1>結點類型（結構）：
struct seg_node {
int l, r, mid, lch, rch, rt;
} T0[MAXN0];
struct SBT_node {
int v, l, r, p, sz0, sz, mul;
} T[MAXN];
其中seg_node是線段樹結點類型，SBT_node是平衡樹(SBT)結點類型。需要注意的是seg_node里面的rt域（root的縮寫），它是該結點內套的平衡樹的根結點下標索引（因為對于任意一棵平衡樹，只要知道了其根結點就可以遍歷整棵樹）。
<2>建樹：
建樹是線段樹和平衡樹一起建。在建立線段樹結點的時候，先建立一棵空的平衡樹（rt域置0），然后再在平衡樹里面逐個插入該結點管轄區(qū)間內的所有元素即可；
<3>修改：
修改操作要注意：如果要將A[x]（A為原序列）的值修改為y，則需要自頂向下遍歷整棵線段樹，將所有包含了A[x]的結點內的平衡樹全部執(zhí)行“刪除v=A[x]（這個可以通過真正維護一個序列得到），再插入y”的操作；
<4>找區(qū)間第K小：
這個操作極其麻煩。需要借助二分。
設要在區(qū)間[l, r]中找到第K小。首先將[l, r]拆分成若干個線段樹結點，然后二分一個值x，在這些結點的平衡樹中找到x的rank（這里的rank指平衡樹中有多少個值比x小，不需要加1），加起來，最后再加1，就是x在[l, r]中的總名次。問題是，設[l..r]中第K小的數為v1，第(K+1)小的數為v2（如果不存在的話，v2=+∞），則[v1, v2)內的數都是“第K小”的。因此，不能二分數字，而應該二分元素。設S[i]為原序列中第i小的數，二分i，然后在根結點的平衡樹中找到第i小的即為S[i]，再求其名次，這樣直到找到總名次為K的元素為止。問題還沒完，序列中可能有元素的值相同，這時可能永遠也找不到第K小的（比如序列1 2 3 3 3 4 5，K=4，若“序列中比x小的元素總數+1”為x的名次，則永遠也找不到第4小的），因此，若這樣求出的“名次”小于等于K，都應該將下一次的左邊界設為mid而不是(mid+1)，而“名次”大于K時，該元素肯定不是第K小的，所以下一次右邊界設為(mid-1)。
代碼（本機測最猥瑣數據4s以內，交到ZJU上TLE，不知為什么，神犇指點一下，3x）：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN0 = 110000, MAXN = 930000, INF = ~0U >> 2;
struct seg_node {
int l, r, mid, lch, rch, rt;
} T0[MAXN0];
struct SBT_node {
int v, l, r, p, sz0, sz, mul;
} T[MAXN];
int No0, No, n, root, rt0, a[MAXN0 >> 1], b[MAXN0 >> 1], l1, r1, len;
void slc(int _p, int _c)
{
T[_p].l = _c; T[_c].p = _p;
}
void src(int _p, int _c)
{
T[_p].r = _c; T[_c].p = _p;
}
void upd(int x)
{
T[x].sz0 = T[T[x].l].sz0 + T[T[x].r].sz0 + T[x].mul;
T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1;
}
void lrot(int x)
{
int y = T[x].p; if (y == rt0) T[rt0 = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
src(y, T[x].l); slc(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void rrot(int x)
{
int y = T[x].p; if (y == rt0) T[rt0 = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
slc(y, T[x].r); src(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void maintain(int x, bool ff)
{
int z;
if (ff) {
if (T[T[T[x].r].r].sz > T[T[x].l].sz) {z = T[x].r; lrot(z);}
else if (T[T[T[x].r].l].sz > T[T[x].l].sz) {z = T[T[x].r].l; rrot(z); lrot(z);} else return;
} else {
if (T[T[T[x].l].l].sz > T[T[x].r].sz) {z = T[x].l; rrot(z);}
else if (T[T[T[x].l].r].sz > T[T[x].r].sz) {z = T[T[x].l].r; lrot(z); rrot(z);} else return;
}
maintain(T[z].l, 0); maintain(T[z].r, 1); maintain(z, 0); maintain(z, 1);
}
int find(int _v)
{
int i = rt0, v0;
while (i) {
v0 = T[i].v;
if (_v == v0) return i; else if (_v < v0) i = T[i].l; else i = T[i].r;
}
return 0;
}
void ins(int _v)
{
if (!rt0) {
T[++No].v = _v; T[No].l = T[No].r = T[No].p = 0; T[No].sz0 = T[No].sz = T[No].mul = 1; rt0 = No;
} else {
int i = rt0, j, v0;
while (1) {
T[i].sz0++; v0 = T[i].v;
if (_v == v0) {T[i].mul++; return;} else if (_v < v0) j = T[i].l; else j = T[i].r;
if (j) i = j; else break;
}
T[++No].v = _v; T[No].l = T[No].r = 0; T[No].sz0 = T[No].sz = T[No].mul = 1; if (_v < v0) slc(i, No); else src(i, No);
while (i) {T[i].sz++; maintain(i, _v > T[i].v); i = T[i].p;}
}
}
void del(int x)
{
if (T[x].mul > 1) {
T[x].mul--;
while (x) {T[x].sz0--; x = T[x].p;}
} else {
int l = T[x].l, r = T[x].r;
if (!l || !r) {
if (x == rt0) T[rt0 = l + r].p = 0; else {
int p = T[x].p; if (x == T[p].l) slc(p, l + r); else src(p, l + r);
while (p) {T[p].sz0--; T[p].sz--; p = T[p].p;}
}
} else {
int i = l, j;
while (j = T[i].r) i = j;
T[x].v = T[i].v; T[x].mul = T[i].mul; int p = T[i].p; if (i == T[p].l) slc(p, T[i].l); else src(p, T[i].l);
while (p) {upd(p); p = T[p].p;}
}
}
}
int Find_Kth(int K)
{
int i = rt0, s0, m0;
while (i) {
s0 = T[T[i].l].sz0; m0 = T[i].mul;
if (K <= s0) i = T[i].l; else if (K <= s0 + m0) return T[i].v; else {K -= s0 + m0; i = T[i].r;}
}
}
int rank(int _v)
{
int i = rt0, tot = 0, v0;
while (i) {
v0 = T[i].v;
if (_v == v0) {tot += T[T[i].l].sz0; return tot;} else if (_v < v0) i = T[i].l; else {tot += T[T[i].l].sz0 + T[i].mul; i = T[i].r;}
}
return tot;
}
int mkt(int l, int r)
{
T0[++No0].l = l; T0[No0].r = r; int mid = l + r >> 1; T0[No0].mid = mid; rt0 = 0;
re3(i, l, r) ins(a[i]); T0[No0].rt = rt0;
if (l < r) {int No00 = No0; T0[No00].lch = mkt(l, mid); T0[No00].rch = mkt(mid + 1, r); return No00;} else {T0[No0].lch = T0[No0].rch = 0; return No0;}
}
void fs(int x)
{
if (x) {
int l0 = T0[x].l, r0 = T0[x].r;
if (l0 >= l1 && r0 <= r1) b[len++] = T0[x].rt; else if (l0 > r1 || r0 < l1) return; else {fs(T0[x].lch); fs(T0[x].rch);}
}
}
void C(int x, int _v)
{
int i = root, l0, r0, mid0, v0 = a[x], N;
while (i) {
l0 = T0[i].l; r0 = T0[i].r; mid0 = T0[i].mid; rt0 = T0[i].rt;
N = find(v0); del(N); ins(_v); T0[i].rt = rt0;
if (x <= mid0) i = T0[i].lch; else i = T0[i].rch;
}
a[x] = _v;
}
int Q(int K)
{
len = 0; fs(root);
int ls = 1, rs = n, mids, midv, tot;
while (ls < rs) {
mids = ls + rs + 1 >> 1; rt0 = T0[root].rt; midv = Find_Kth(mids);
tot = 1; re(i, len) {rt0 = b[i]; tot += rank(midv);}
if (tot <= K) ls = mids; else rs = mids - 1;
}
rt0 = T0[root].rt; return Find_Kth(ls);
}
int main()
{
int tests, m, x, y, K;
char ch;
scanf("%d", &tests);
re(testno, tests) {
scanf("%d%d", &n, &m); No0 = No = 0;
re(i, n) scanf("%d", &a[i]); ch = getchar();
root = mkt(0, n - 1);
re(i, m) {
ch = getchar();
if (ch == 'C') {
scanf("%d%d%*c", &x, &y);
C(--x, y);
} else {
scanf("%d%d%d%*c", &l1, &r1, &K);
l1--; r1--; printf("%d\n", Q(K));
}
}
}
return 0;
}