Dynamic Ranking

#include <bits/stdc++.h>using namespace std;#define maxn 10005#define maxtot maxn*600struct QueryType {    int l,r,k;    char op[4];};struct QueryType qu[maxn];int n,m,ai[maxn],bi[maxn<<1],root[maxn];int posl[100],numl,posr[100],numr,lc[maxtot];int rc[maxtot],dis[maxtot],tot,cnt,size;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>‘9‘||Cget<‘0‘) Cget=getchar();    while(Cget>=‘0‘&&Cget<=‘9‘)    {        now=now*10+Cget-‘0‘;        Cget=getchar();    }}inline int lowbit(int x){    return x&(-x);}inline void add(int &now,int l,int r,int to,int x){    if(!now) now=++tot;dis[now]+=x;    if(l==r) return;int mid=l+r>>1;    if(to<=mid) add(lc[now],l,mid,to,x);    else add(rc[now],mid+1,r,to,x);}inline void tree_add(int x,int to,int di){    while(x<=n)    {        add(root[x],1,size,to,di);        x+=lowbit(x);    }}inline void pre(int l,int r){    l--,numl=0,numr=0;    while(r) posr[++numr]=root[r],r-=lowbit(r);    while(l) posl[++numl]=root[l],l-=lowbit(l);}inline int query(int l,int r,int k){    if(l==r) return bi[l];    int di=0,mid=l+r>>1;    for(int i=1;i<=numr;i++) di+=dis[lc[posr[i]]];    for(int i=1;i<=numl;i++) di-=dis[lc[posl[i]]];    if(k<=di)    {        for(int i=1;i<=numr;i++) posr[i]=lc[posr[i]];        for(int i=1;i<=numl;i++) posl[i]=lc[posl[i]];        return query(l,mid,k);    }    else    {        for(int i=1;i<=numr;i++) posr[i]=rc[posr[i]];        for(int i=1;i<=numl;i++) posl[i]=rc[posl[i]];        return query(mid+1,r,k-di);    }}int main(){    in(n),in(m);    for(int i=1;i<=n;i++) in(ai[i]),bi[++cnt]=ai[i];    for(int i=1;i<=m;i++)    {        scanf("%s",qu[i].op),in(qu[i].l),in(qu[i].r);        if(qu[i].op[0]==‘Q‘) in(qu[i].k);        else bi[++cnt]=qu[i].r;    }    sort(bi+1,bi+cnt+1),size=unique(bi+1,bi+cnt+1)-bi-1;    for(int i=1;i<=n;i++)    {        ai[i]=lower_bound(bi+1,bi+size+1,ai[i])-bi;        tree_add(i,ai[i],1);    }    for(int i=1;i<=m;i++)    {        if(qu[i].op[0]==‘Q‘)        {            pre(qu[i].l,qu[i].r);            printf("%d\n",query(1,size,qu[i].k));        }        else        {            qu[i].r=lower_bound(bi+1,bi+size+1,qu[i].r)-bi;            tree_add(qu[i].l,ai[qu[i].l],-1);            ai[qu[i].l]=qu[i].r;            tree_add(qu[i].l,qu[i].r,1);        }    }    return 0;}