学步园

题目大意：带修改的区间第k大

就是树状数组套可持久线段树 

#include<cstdio>
#include<iostream>
using namespace std;
const int maxt=10000011,maxn=1e9,maxm=10011,maxch=maxt;
char buf[maxch],*wbuf=buf;
inline void read(int &x){
    x=0;while (*wbuf<'0'||*wbuf>'9') ++wbuf;
    while ('0'<=*wbuf&&*wbuf<='9')x=x*10+*wbuf++-'0';
}
inline void getch(char &ch){
    while (*wbuf!='Q'&&*wbuf!='C') ++wbuf;ch=*wbuf;
}
int size[maxt],lson[maxt],rson[maxt];
int tot;
void ins(int p,int l,int r,int m,int add){
    size[p]+=add;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (m<=mid) ins(lson[p]?lson[p]:lson[p]=++tot,l,mid,m,add);
    else ins(rson[p]?rson[p]:rson[p]=++tot,mid+1,r,m,add);
}
int p1[17],p2[17];
void query(int a,int b,int c){
    int sum1=0,sum2=0,l=0,r=maxn;
    for (int i=a-1;i;i-=i&(-i)) p1[++sum1]=i;
    for (int i=b;i;i-=i&(-i)) p2[++sum2]=i;
    while (l<r){
        int mid=(l+r)>>1,rank=0;
        for (int i=1;i<=sum1;++i) rank-=size[lson[p1[i]]];
        for (int i=1;i<=sum2;++i) rank+=size[lson[p2[i]]];
        if (c<=rank){
            r=mid;
            for (int i=1;i<=sum1;++i) p1[i]=lson[p1[i]];
            for (int i=1;i<=sum2;++i) p2[i]=lson[p2[i]];
        }else{
            l=mid+1;c-=rank;
            for (int i=1;i<=sum1;++i) p1[i]=rson[p1[i]];
            for (int i=1;i<=sum2;++i) p2[i]=rson[p2[i]];
        }
    }
    printf("%d\n",l);
}
int n,m;
int a[maxm];
void init(){
	fread(buf,1,maxch,stdin);
    read(n);read(m);tot=n;
    for (int i=1;i<=n;++i){
        read(a[i]);
        for (int j=i;j<=n;j+=j&(-j))
            ins(j,0,maxn,a[i],1);
    }
}
void work(){
    char op;int x,y,z;
    while (m--){
        getch(op);
        if (op=='C'){
            read(x);read(y);
            for (int i=x;i<=n;i+=i&(-i)){
                ins(i,0,maxn,y,1);ins(i,0,maxn,a[x],-1);
            }
            a[x]=y;
        }
        else{read(x);read(y);read(z);query(x,y,z);}
    }
}
int main(){
    init();
    work();
    return 0;
}