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=;

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') x=x*+(c^),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+,r,x,v);

}

int Ask(int l,int r,int k){

    if(l==r) return b[l];

    int re=;

    for(rint i=;i<=tx;++i) re-=siz[lc[X[i]]];

    for(rint i=;i<=ty;++i) re+=siz[lc[Y[i]]];

    if(k<=re){

        for(rint i=;i<=tx;++i) X[i]=lc[X[i]];

        for(rint i=;i<=ty;++i) Y[i]=lc[Y[i]];

        return Ask(l,mid,k);

    }else{

        for(rint i=;i<=tx;++i) X[i]=rc[X[i]];

        for(rint i=;i<=ty;++i) Y[i]=rc[Y[i]];

        return Ask(mid+,r,k-re);

    }

}

void add(int x,int v){

    int k=lower_bound(b+,b+tn+,a[x])-b;

    for(int i=x;i<=n;i+=i&-i) ins(rt[i],,tn,k,v);

}

int main(){

    read(n);read(m); char opt[];

    for(rint i=;i<=n;++i) read(a[i]),b[++tn]=a[i];

    for(rint i=;i<=m;++i){

        scanf("%s",opt); read(p1[i]),read(p2[i]);

        if(opt[]=='Q') read(p3[i]);

        else b[++tn]=p2[i];

    }sort(b+,b+tn+);

    tn=unique(b+,b+tn+)-b-;//离散化

    for(rint i=;i<=n;++i) add(i,);

    for(rint i=;i<=m;++i){

        if(p3[i]){

            tx=ty=;

            for(int j=p1[i]-;j;j-=j&-j) X[++tx]=rt[j];

            for(int j=p2[i];j;j-=j&-j) Y[++ty]=rt[j];

            printf("%d\n",Ask(,tn,p3[i]));

        }else{

            add(p1[i],-);

            a[p1[i]]=p2[i];

            add(p1[i],);

        }

    }

}