P2617 Dynamic Rankings（树状数组套主席树）

P2617 Dynamic Rankings

单点修改，区间查询第k大

当然是无脑树套树了~

树状数组套主席树就好辣

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rint register int
using namespace std;
void read(int &x){
    char c=getchar();x=0;
    while(c<'0'||c>'9') c=getchar();
    while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
}
#define N 200005
#define W 60000005
int n,m,p1[N],p2[N],p3[N],a[N],tn,b[N];
int u,rt[N],lc[W],rc[W],siz[W],tx,ty,X[N],Y[N];
#define mid (l+r)/2
void ins(int &o,int l,int r,int x,int v){
    if(!o) o=++u;
    siz[o]+=v;
    if(l==r) return ;
    if(x<=mid) ins(lc[o],l,mid,x,v);
    else ins(rc[o],mid+1,r,x,v);
}
int Ask(int l,int r,int k){
    if(l==r) return b[l];
    int re=0;
    for(rint i=1;i<=tx;++i) re-=siz[lc[X[i]]];
    for(rint i=1;i<=ty;++i) re+=siz[lc[Y[i]]];
    if(k<=re){
        for(rint i=1;i<=tx;++i) X[i]=lc[X[i]];
        for(rint i=1;i<=ty;++i) Y[i]=lc[Y[i]];
        return Ask(l,mid,k);
    }else{
        for(rint i=1;i<=tx;++i) X[i]=rc[X[i]];
        for(rint i=1;i<=ty;++i) Y[i]=rc[Y[i]];
        return Ask(mid+1,r,k-re);
    }
}
void add(int x,int v){
    int k=lower_bound(b+1,b+tn+1,a[x])-b;
    for(int i=x;i<=n;i+=i&-i) ins(rt[i],1,tn,k,v); 
}
int main(){
    read(n);read(m); char opt[3];
    for(rint i=1;i<=n;++i) read(a[i]),b[++tn]=a[i];
    for(rint i=1;i<=m;++i){
        scanf("%s",opt); read(p1[i]),read(p2[i]);
        if(opt[0]=='Q') read(p3[i]);
        else b[++tn]=p2[i];
    }sort(b+1,b+tn+1);
    tn=unique(b+1,b+tn+1)-b-1;//离散化
    for(rint i=1;i<=n;++i) add(i,1);
    for(rint i=1;i<=m;++i){
        if(p3[i]){
            tx=ty=0;
            for(int j=p1[i]-1;j;j-=j&-j) X[++tx]=rt[j];
            for(int j=p2[i];j;j-=j&-j) Y[++ty]=rt[j];
            printf("%d
",Ask(1,tn,p3[i]));
        }else{
            add(p1[i],-1);
            a[p1[i]]=p2[i];
            add(p1[i],1);
        }
    }
}