[ZOJ 2112] Dynamic Rankings 트 리 세트 주석 트 리

동적 조회 구간 k 가 크다.먼저 주석 트 리 로 정적 인 상황 을 저장 한 다음 에 트 리 배열 로 주석 트 리 로 수정 작업 을 저장 하고 공간 복잡 도 는 O (n * logn + q * logn * logn) 입 니 다.주석 트 리 자체 가 접두사 와 성질 이 있 는 데이터 구조 이기 때문에 트 리 배열 을 추가 할 수 있 고 트 리 배열 의 노드 는 선분 트 리 입 니 다.한 번 수 정 된 시공 간 복잡 도 는 O (logn * logn) 입 니 다.

#include
using namespace std;
const int maxn = 60010;
int a[maxn],b[maxn];
struct op{
    int f,i,j,k;
}op[10010];
int ls[2500010],rs[2500010],cnt[2500010],root[maxn],tot,S[maxn];
int idx[maxn],n,N;
void build(int l,int r,int &rt){
    rt = ++tot;
    cnt[rt] = 0;
    if(l == r) return;
    int m = (l+r)>>1;
    build(l,m,ls[rt]);
    build(m+1,r,rs[rt]);
}
void update(int last,int l,int r,int &rt,int p,int x){
    rt = ++tot;
    ls[rt] = ls[last];
    rs[rt] = rs[last];
    cnt[rt] = cnt[last] + x;
    if(l == r) return;
    int m = (l+r)>>1;
    if(p<=m) update(ls[last],l,m,ls[rt],p,x);
    else update(rs[last],m+1,r,rs[rt],p,x);
}
void add(int i,int p,int x){
    for(;i<=n;i+=i&-i){
        update(S[i],1,N,S[i],p,x);
    }
}
int getsum(int i){
    int ret = 0;
    for(;i;i-=i&-i){
        ret += cnt[ls[idx[i]]];
    }
    return ret;
}
int query(int ll,int rr,int k){
    for(int i = ll;i;i-=i&-i) idx[i] = S[i];
    for(int i = rr;i;i-=i&-i) idx[i] = S[i];
    int l = 1,r = N,L = root[ll],R = root[rr];
    while(lint c = cnt[ls[R]] - cnt[ls[L]] + getsum(rr) - getsum(ll);
        int m = (l+r)>>1;
        if(c >= k){
            for(int i = ll;i;i-=i&-i) idx[i] = ls[idx[i]];
            for(int i = rr;i;i-=i&-i) idx[i] = ls[idx[i]];
            L = ls[L],R = ls[R];
            r = m;
        }else{
            for(int i = ll;i;i-=i&-i) idx[i] = rs[idx[i]];
            for(int i = rr;i;i-=i&-i) idx[i] = rs[idx[i]];
            k -= c;
            L = rs[L],R = rs[R];
            l = m+1;
        }
    }
    return l;
}
int getid(int x){
    return lower_bound(b+1,b+N+1,x)-b;
}
char str[3];
int main(){
    int T,m;
    scanf("%d",&T);
    while(T--){
        tot = 0;
        scanf("%d%d",&n,&m);
        for(int i = 1;i<=n;i++){
            scanf("%d",a+i);
            b[i] = a[i];
        }
        N = n;
        for(int i = 0;i<m;i++){
            scanf("%s",str);
            if(str[0] == 'Q'){
                scanf("%d%d%d",&op[i].i,&op[i].j,&op[i].k);
                op[i].f = 0;
            }
            else{
                scanf("%d%d",&op[i].i,&op[i].k);
                b[++N] = op[i].k;
                op[i].f = 1;
            }
        }
        sort(b+1,b+N+1);
        N = unique(b+1,b+N+1)-b-1;
        build(1,N,root[0]);
        for(int i = 1;i<=n;i++){
            update(root[i-1],1,N,root[i],getid(a[i]),1);
        }
        for(int i = 1;i<=n;i++) S[i] = root[0];
        for(int i = 0;i<m;i++){
            if(op[i].f){
                add(op[i].i,getid(a[op[i].i]),-1);
                add(op[i].i,getid(op[i].k),1);
                a[op[i].i] = op[i].k;
            }else{
                printf("%d
",b[query(op[i].i-1,op[i].j,op[i].k)]);
            }
        }
    }
}