题目链接：https://vjudge.net/problem/ZOJ-2112
多样例：
输入一个样例数t。
输入一个n和m。数组长度和操作数
Q l r k：查询区间[l, r]的第k小的数
C x y：修改a[x]=y

Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6

思路：整体二分的模板题

#include <bits/stdc++.h>  
using namespace std;  
#define  LL long long  
const int maxn=5e5+10, maxm=1e5+10, inf=1e9+7;  

struct node{  
    int x, y, k, type, id;  
}q[maxn+maxm*2], q1[maxn+maxm*2], q2[maxn+maxm*2];  

int n, m, tot, totx;  
int a[maxn], ans[maxn];  

struct BitTree  {  
    LL c[maxn];  
    int lowbit(int p){  
        return (p&-p);  
    }  
    void Add(int x, LL v)  
    {  
        if (!x)  
            return;  
        while (x < 500005)  
            c[x] += v, x += lowbit(x);  
    }  
    LL Ask(int x)  
    {  
        LL t = 0;  
        while (x)  
            t += c[x], x -= lowbit(x);  
        return t;  
    }  
    LL Ask(int l, int r)  
    {  
        if (l > r)  
            return 0;  
        return Ask(r) - Ask(l - 1);  
    }  
}Tree;  


void solve(int ql, int qr, int L, int R){  
    if(ql>qr) return ;  
    if(L==R){//统计答案  
        for(int i=ql; i<=qr; i++){  
            if(q[i].type==2){  
                ans[q[i].id]=L;  
            }  
        }  
        return ;  
    }  
    int mid=(L+R)>>1;  
    int t1=0, t2=0;  
    for(int i=ql; i<=qr; i++){//按顺序执行一边  
        if(q[i].type==1){//遇见修改  
            if(q[i].x<=mid){//<mid 对结果产生影响  
                Tree.Add(q[i].id, q[i].y);  
                q1[t1++]=q[i];  
            }  
            else{//不产生影响  
                q2[t2++]=q[i];  
            }  
        }  
        else{//遇见查询  
            int tt=Tree.Ask(q[i].x, q[i].y);//查询区间下标在[x, y]<=mid的数的个数  
            if(tt>=q[i].k) q1[t1++]=q[i];//如果>=k个  
            else{//如果<k个  
                q[i].k-=tt;  
                q2[t2++]=q[i];  
            }  
        }  
    }  
    for(int i=0; i<t1; i++) q[ql+i]=q1[i]; //把q1,q2的信息复制到q中  
    for(int i=0; i<t2; i++) q[ql+t1+i]=q2[i];  
    for(int i=0; i<t1; i++){  
        if(q1[i].type==1){  
            Tree.Add(q1[i].id, -q1[i].y);//把之前的标记清除  
        }  
    }  
    solve(ql, ql+t1-1, L, mid);//分治  
    solve(ql+t1, qr, mid+1, R);  
}  

int main(){  
    int T; scanf("%d", &T);  
    while(T--){  
        tot=totx=0;  
        scanf("%d%d", &n, &m);  
        int x, y, k;  
        char op[5];  
        for(int i=1; i<=n; i++){  
            scanf("%d", &a[i]);  
            tot++;  
            q[tot].x=a[i], q[tot].y=1, q[tot].type=1, q[tot].id=i;  
            //x:值   y：添加还是删除 type:查询还是修改 id:下标  
        }  
        for(int i=1; i<=m; i++){  
            scanf("%s", op);  
            if(op[0]=='Q'){  
                scanf("%d%d%d", &x, &y, &k);  
                tot++;  
                q[tot].x=x, q[tot].y=y, q[tot].k=k, q[tot].type=2, q[tot].id=++totx;  
            }  
            else{  
                scanf("%d%d", &x, &y);  
                tot++;  
                q[tot].x=a[x]; q[tot].y=-1; q[tot].type=1, q[tot].id=x;  
                tot++;  
                a[x]=y;  
                q[tot].x=a[x]; q[tot].y=1; q[tot].type=1, q[tot].id=x;  
            }  
        }  
        solve(1, tot, 0, inf);  
        for(int i=1; i<=totx; i++){  
            printf("%d\n", ans[i]);  
        }  
    }  

    return 0;  
}