P2617 Dynamic Ranking(树状数组套主席树模板)

2017-12-25 19:22:56


我是看这个学会的:https://www.cnblogs.com/Empress/p/4659824.html

树状数组套主席树可以实现带修改的主席树

树状数组每个元素内含一颗权值线段树,初始化逐个动态加点,修改同理,空间复杂度 O(nlognlogn)

然而我并不知道这和主席树有什么关系

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn=10010;
    int n,m,a[maxn];
    int hash[maxn*2],hashN;
    inline int read(){
        int ret=0,sign=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-') sign=-1;
            else if(ch=='Q'||ch=='C') return ch;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
        return ret*sign;
    }
    struct Cmd{
        char op;
        int x,y,z;
    }cmd[maxn];
    struct node{
        int val,l,r,son[2];
        node(){}
        node(int _l,int _r){l=_l,r=_r,val=son[0]=son[1]=0;}
    }T[maxn*400];
    int root[maxn],cnt;
    void ins(int op,int &u,int l,int r,int x){
        if(!u) u=++cnt,T[u]=node(l,r);
        T[u].val+=op;
        int mid=(T[u].l+T[u].r)>>1;
        if(l==r) return;
        if(x<=mid) ins(op,T[u].son[0],l,mid,x);
        else ins(op,T[u].son[1],mid+1,r,x);
    }
    inline int lbt(int x){return x&(-x);}
    void add(int op,int u,int x){while(u<=n) ins(op,root[u],1,hashN,x),u+=lbt(u);}
    int tmpP[2][20],rtN[2];
    int query(int l,int r,int k){
        rtN[0]=rtN[1]=0;
        for(int i=l-1;i;i-=lbt(i)) tmpP[0][++rtN[0]]=root[i];
        for(int i=r;i;i-=lbt(i)) tmpP[1][++rtN[1]]=root[i];
        int vl=1,vr=hashN;
        while(vl!=vr){
            int mid=(vl+vr)>>1,lsum[2]={0},rela;
            for(int i=0;i<=1;i++)
                for(int j=1;j<=rtN[i];j++)
                    lsum[i]+=T[T[tmpP[i][j]].son[0]].val;
            rela=k>lsum[1]-lsum[0];
            if(rela) k-=lsum[1]-lsum[0],vl=mid+1;
            else vr=mid;
            for(int i=0;i<=1;i++)
                for(int j=1;j<=rtN[i];j++)
                    tmpP[i][j]=T[tmpP[i][j]].son[rela];
        }
        return vl;
    }
    int main(){
        n=read(),m=read();
        for(int i=1;i<=n;i++)
            hash[i]=a[i]=read();
        hashN=n;
        for(int i=1;i<=m;i++){
            cmd[i].op=read();
            if(cmd[i].op=='Q') cmd[i].x=read(),cmd[i].y=read(),cmd[i].z=read();
            else cmd[i].x=read(),hash[++hashN]=cmd[i].y=read();
        }
        sort(hash+1,hash+hashN+1);
        hashN=unique(hash+1,hash+hashN+1)-hash-1;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(hash+1,hash+hashN+1,a[i])-hash;
            add(1,i,a[i]);
        }
        for(int i=1;i<=m;i++){
            if(cmd[i].op=='Q') printf("%d\n",hash[query(cmd[i].x,cmd[i].y,cmd[i].z)]);
            else cmd[i].y=lower_bound(hash+1,hash+hashN+1,cmd[i].y)-hash,add(-1,cmd[i].x,a[cmd[i].x]),add(1,cmd[i].x,cmd[i].y),a[cmd[i].x]=cmd[i].y;
        }
        return 0;
    }

这个空间复杂度是可以优化的 用静态主席树维护原序列,空间复杂度 O(nlogn)

树状数组保存修改部分,树状数组每个元素内含一颗权值线段树,需要修改时动态加点,空间复杂度 O(mlognlogn)

查询时tmp1存当前到原树的结点,tmp2预处理出树状数组要修改的logn个结点,两部分加起来就是实际值

总空间复杂度 O(nlogn+mlognlogn) ,当m较小时效果明显

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn=10010;
    int n,m,a[maxn];
    int hash[maxn*2],hashN;
    inline int read(){
        int ret=0,sign=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-') sign=-1;
            if(ch=='Q'||ch=='C') return ch;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();}
        return ret*sign;
    }
    struct Cmd{
        char op;
        int x,y,z;
    }cmd[maxn];
    struct node{
        int val,son[2];
    }T1[maxn*20],T2[maxn*400];
    int root1[maxn],root2[maxn],cnt1,cnt2;
    void build(int &u,int l,int r){
        u=++cnt1;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(T1[u].son[0],l,mid);
        build(T1[u].son[1],mid+1,r);
    }
    void ins1(int &u,int v,int l,int r,int x){
        u=++cnt1,T1[u]=T1[v],++T1[u].val;
        int mid=(l+r)>>1;
        if(l==r) return;
        if(x<=mid) ins1(T1[u].son[0],T1[v].son[0],l,mid,x);
        else ins1(T1[u].son[1],T1[v].son[1],mid+1,r,x);
    }
    void ins2(int &u,int l,int r,int x,int op){
        if(!u) u=++cnt2;
        T2[u].val+=op;
        int mid=(l+r)>>1;
        if(l==r) return;
        if(x<=mid) ins2(T2[u].son[0],l,mid,x,op);
        else ins2(T2[u].son[1],mid+1,r,x,op);
    }
    inline int lbt(int x){return x&-x;}
    inline void add(int u,int x,int op){while(u<=n) ins2(root2[u],1,hashN,x,op),u+=lbt(u);}
    int tmp1[2],tmp2[2][20],tmpN[2];
    int query(int l,int r,int k){
        tmpN[0]=tmpN[1]=0;
        tmp1[0]=root1[l-1],tmp1[1]=root1[r];
        for(int i=l-1;i;i-=lbt(i)) tmp2[0][++tmpN[0]]=root2[i];
        for(int i=r;i;i-=lbt(i)) tmp2[1][++tmpN[1]]=root2[i];
        int vl=1,vr=hashN;
        while(vl!=vr){
            int lsum=T1[T1[tmp1[1]].son[0]].val-T1[T1[tmp1[0]].son[0]].val;
            for(int i=1;i<=tmpN[0];i++)
                lsum-=T2[T2[tmp2[0][i]].son[0]].val;
            for(int i=1;i<=tmpN[1];i++)
                lsum+=T2[T2[tmp2[1][i]].son[0]].val;
            int rela=k>lsum;
            if(rela) k-=lsum,vl=((vl+vr)>>1)+1;
            else vr=(vl+vr)>>1;
            tmp1[0]=T1[tmp1[0]].son[rela],tmp1[1]=T1[tmp1[1]].son[rela];
            for(int i=1;i<=tmpN[0];i++)
                tmp2[0][i]=T2[tmp2[0][i]].son[rela];
            for(int i=1;i<=tmpN[1];i++)
                tmp2[1][i]=T2[tmp2[1][i]].son[rela];
            //cout<<vl<<' '<<vr<<endl;
        }
        return vl;
    }
    int main(){
        n=read(),m=read();
        for(int i=1;i<=n;i++)
            hash[i]=a[i]=read();
        hashN=n;
        for(int i=1;i<=m;i++){
            cmd[i].op=read();
            if(cmd[i].op=='Q') cmd[i].x=read(),cmd[i].y=read(),cmd[i].z=read();
            else cmd[i].x=read(),hash[++hashN]=cmd[i].y=read();
        }
        sort(hash+1,hash+hashN+1);
        hashN=unique(hash+1,hash+hashN+1)-hash-1;
        build(root1[0],1,hashN);
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(hash+1,hash+hashN+1,a[i])-hash;
            ins1(root1[i],root1[i-1],1,hashN,a[i]);
        }
        for(int i=1;i<=m;i++){
            if(cmd[i].op=='Q') printf("%d\n",hash[query(cmd[i].x,cmd[i].y,cmd[i].z)]);
            else{
                cmd[i].y=lower_bound(hash+1,hash+hashN+1,cmd[i].y)-hash;
                add(cmd[i].x,a[cmd[i].x],-1),add(cmd[i].x,cmd[i].y,1);
                a[cmd[i].x]=cmd[i].y;
            }
        }
        return 0;
    }