记录编号	562439	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.384 s
提交时间	2021-07-05 10:53:54	内存使用	40.60 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 500005;
struct Q{
    int op,x,y,z;
    Q() {
        op = x = y = z = 0;
    }
}query[maxn],lq[maxn],rq[maxn];
struct q2 {
    char c;
    int x,y,z;
    q2() {
        x = y = z = 0;
        c = ' ';
    }
}q[maxn];
int n,m,C[maxn],a[maxn],ans[maxn],c[maxn],t;
bool vis[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int x,int y) {
    for(;x <= n;x += lowbit(x))c[x] += y;
    return ;
}
int ask(int x) {
    int tot = 0;
    for(;x;x -= lowbit(x)) {
        tot += c[x];
    }
    return tot;
}
void solve(int l,int r,int st,int ed) {
    if(st > ed)return ;
    if(l == r) {
        for(int i = st;i <= ed;++ i) {
            if(query[i].op > 0) {
                ans[query[i].op] = C[l];
            }
        }
        return ;
    }
    int mid = l + r >> 1;
    int lt = 0,rt = 0;
    for(int i = st;i <= ed;++ i) {
        if(query[i].op == -1) {
            if(query[i].y <= mid) {
                add(query[i].x , -1);
                lq[++ lt] = query[i];
            }
            else rq[++ rt] = query[i];
        }
        else if(query[i].op == 0) {
            if(query[i].y <= mid) {
                add(query[i].x , 1);
                lq[++ lt] = query[i];
            }
            else {
                rq[++ rt] = query[i];
            }
        }
        else {
            int cnt = ask(query[i].y) - ask(query[i].x - 1);
            if(cnt >= query[i].z) {
                lq[++ lt] = query[i];
            }
            else {
                query[i].z -= cnt;
                rq[++ rt] = query[i];
            }
        }
    }
    for(int i = st;i <= ed;++ i) {
        if(query[i].op < 0) {
            if(query[i].y <= mid) {
                add(query[i].x , 1);
            }
        }
        else if(!query[i].op) {
            if(query[i].y <= mid) {
                add(query[i].x , -1);
            }
        }
    }
    for(int i = 1;i <= lt;++ i) {
        query[st + i - 1] = lq[i];
    }
    for(int i = 1;i <= rt;++ i) {
        query[st + lt + i - 1] = rq[i];
    }
    solve(l , mid , st , st + lt - 1);
    solve(mid + 1 , r , st + lt , ed);
    return ;
}
void work(void) {
    memset(c , 0 , sizeof(c));
    int cnt = 0;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++ i) {
        scanf("%d",&query[i].y);
        a[i] = query[i].y;
        query[i].x = i;
        query[i].op = 0;
        C[++ cnt] = query[i].y;
    }
    t = n;
    for(int i = 1;i <= m;++ i) {
        char cc;
        int x,y,z;
        scanf(" %c%d%d",&cc,&x,&y);
        q[i].c = cc;
        q[i].x = x;
        q[i].y = y;
        if(cc == 'C') {
            C[++ cnt] = y;
        }
        else {
            scanf("%d",&q[i].z);
        }
    }
    sort(C + 1 , C + 1 + cnt);
    cnt = unique(C + 1 , C + 1 + cnt) - C - 1;
    for(int i = 1;i <= n;++ i) {
        a[i] = query[i].y = lower_bound(C + 1 , C + 1 + cnt , query[i].y) - C;
    }
    int tot = 0;
    for(int i = 1;i <= m;++ i) {
        if(q[i].c == 'C') {                  
            query[++ t].op = -1;
            query[t].x = q[i].x;
            query[t].y = a[q[i].x];
            query[++ t].op = 0;
            query[t].x = q[i].x;
            query[t].y = lower_bound(C + 1 , C + 1 + cnt , q[i].y) - C;
            a[q[i].x] = query[t].y;
        }
        else {
            query[++ t].op = ++ tot;
            query[t].x = q[i].x;       
            query[t].y = q[i].y;
            query[t].z = q[i].z;
        }
    }
    solve(1 , cnt , 1 , t);
    for(int i = 1;i <= tot;++ i) {  
        printf("%d\n",ans[i]);
    }
    return ;
}
int main() {
    freopen("dynrank.in","r",stdin);
    freopen("dynrank.out","w",stdout);
    int d;
    scanf("%d",&d);
    while(d --)work();
    fclose(stdin);
    fclose(stdout);
    return 0;
}