题解 P2617 【Dynamic Ranking】

· · 题解

光说树状数组套主席树对于初学者是很难理解的，比如蒟蒻我。

但是我觉得这种做法的核心思想就是类比像用优化动态前缀和，我们规定root[i]维护的是[i-lowbit(i),i]这段区间的主席树，而不是静态主席那样维护[1..i]，由于洛谷空间卡的松，直接弄弄就行了，不需要其他的优化。

如果你还是不太清楚，可以看看这篇博客，我觉得写的还不错：http://blog.csdn.net/no1\_terminator/article/details/77606822

参考代码（嗯【手动害羞⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄】，高仿楼下dalao）：

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=10100;
int n,m,totx,toty,tn,T_cnt=1;
struct TreeNode{
    int L,R,sum;
}T[N*600];
int x[N],y[N],root[N],ql[N],qr[N],qt[N],a[N],b[N<<1];
char s[10];
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
void insert(int &now,int x,int index,int l=1,int r=tn){
    T[T_cnt++]=T[now];now=T_cnt-1;
    T[now].sum+=index;
    if (l==r)return;
    int mid=(l+r)>>1;
    if (x<=mid)insert(T[now].L,x,index,l,mid);
        else insert(T[now].R,x,index,mid+1,r);
}
void add(int x,int index){
    int pos=lower_bound(b+1,b+tn+1,a[x])-b;
    for (int i=x;i<=n;i+=i&(-i))
        insert(root[i],pos,index);
}
int query(int k,int l=1,int r=tn){
    if (l==r)return l;
    int sum=0,mid=(l+r)>>1;
    for (int i=1;i<=totx;i++)sum-=T[T[x[i]].L].sum;
    for (int i=1;i<=toty;i++)sum+=T[T[y[i]].L].sum;
    if (k<=sum){
        for (int i=1;i<=totx;i++)x[i]=T[x[i]].L;
        for (int i=1;i<=toty;i++)y[i]=T[y[i]].L;
        return query(k,l,mid);
    }else{
        for (int i=1;i<=totx;i++)x[i]=T[x[i]].R;
        for (int i=1;i<=toty;i++)y[i]=T[y[i]].R;
        return query(k-sum,mid+1,r);
    }
}
int main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++)
        b[i]=a[i]=read();
    tn=n;
    for (int i=1;i<=m;i++){
        scanf("%s",s);
        ql[i]=read(),qr[i]=read();//s='Q'  ql->l,qr->r,qt->k          s='C'  ql->x  qr->k
        if (s[0]=='Q')qt[i]=read();
            else b[++tn]=qr[i];
    }
    sort(b+1,b+tn+1);
    tn=unique(b+1,b+tn+1)-b-1;
    for (int i=1;i<=n;i++)add(i,1);
    for (int i=1;i<=m;i++){
        if (qt[i]){
            totx=toty=0;
            for (int j=ql[i]-1;j;j-=j&(-j))x[++totx]=root[j];
            for (int j=qr[i];j;j-=j&(-j))y[++toty]=root[j];
            printf("%d\n",b[query(qt[i])]);
        }else{
            add(ql[i],-1);
            a[ql[i]]=qr[i];
            add(ql[i],1);
        }
    }
    return 0;
}