Dynamic_Rankings(动态区间第k大)

ZOJ - 2112

\[\
\]

(那些说这道题是树状数组套主席树的人一定对主席树有误解!)

这里我们用树状数组套线段树来解决来写

首先 , 我们需要有n棵线段树(不是$n^2$空间,别慌)

我们用这些线段树存储值域$ [l,r] $内数的个数

基于主席树的思想,我们的线段树是要相减的,记录的是前缀

由于要更新前缀,我们必须快速更新,所以采用树状数组来写

事实上,这里线段树的本质并非主席树,而是动态开点的线段树

(这两者是有显著差异的)

这是主席数的单点修改

struct Functional_SegmentTree{

    void Add(int p,int pre,int l,int r,int x,int y){

        s[p]=s[pre]+y;

        if(l==r) return;

        int mid=(l+r)>>1;

        if(x<=mid) rs[p]=rs[pre],Add(ls[p]=++cnt,ls[pre],l,mid,x,y);

        else ls[p]=ls[pre],Add(rs[p]=++cnt,rs[pre],mid+1,r,x,y);

    }

};

是路径上的所有点都要新开节点,而实际上动点线段树不是开新点,只是当你的儿子要访问了却还未开出来时才需要开

所以代码应该是这样的

void Add(int p,int l,int r,int x,int y){

    s[p]+=y;

    if(l==r) return;

    int mid=(l+r)>>1;

    if(x<=mid) Add(ls[p]?ls[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,ls[p]=++cnt),l,mid,x,y);

    else Add(rs[p]?rs[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,rs[p]=++cnt),mid+1,r,x,y);

}

(略有压行)

所以整体上应该是树状数组更新动点线段树

但是由于这题卡空间 (过于罪恶)

所以我们应该先开一个主席树存下原来的值

(为什么这样能省空间呢?因为树状数组更新的空间复杂度是$log^2(n)$，主席树更新是log(n)的)

于是代码会长这样

const int N=50100,M=10010,K=1520110;

int n,m;

int ncnt;

int a[N],b[N+M],c[M],d[M],e[M];

int cnt;

int ls[K],rs[K],s[K];

int rt[N];

struct hjt{

    void Add(int p,int pre,int l,int r,int x,int y){

        s[p]=s[pre]+y;

        if(l==r) return;

        int mid=(l+r)>>1;

        if(x<=mid) rs[p]=rs[pre],Add(ls[p]=++cnt,ls[pre],l,mid,x,y);

        else ls[p]=ls[pre],Add(rs[p]=++cnt,rs[pre],mid+1,r,x,y);

    }

}H;

struct sts{

    void Add(int p,int l,int r,int x,int y){

        s[p]+=y;

        if(l==r) return;

        int mid=(l+r)>>1;

        if(x<=mid) Add(ls[p]?ls[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,ls[p]=++cnt),l,mid,x,y);

        else Add(rs[p]?rs[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,rs[p]=++cnt),mid+1,r,x,y);

    }

    int T[N];

    vector <int> X,Y;

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

        if(l==r) return l;

        int mid=(l+r)>>1;

        int t=0;

        rep(i,0,X.size()-1) t+=s[ls[X[i]]];

        rep(i,0,Y.size()-1) t-=s[ls[Y[i]]];

        if(t>=k) {

            rep(i,0,X.size()-1) X[i]=ls[X[i]];

            rep(i,0,Y.size()-1) Y[i]=ls[Y[i]];

            return Que(l,mid,k);

        } else {

            rep(i,0,X.size()-1) X[i]=rs[X[i]];

            rep(i,0,Y.size()-1) Y[i]=rs[Y[i]];

            return Que(mid+1,r,k-t);

        }

    }

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

        int p=r; X.clear();X.push_back(rt[r]);

        while(p) X.push_back(T[p]),p-=p&-p;

        p=l-1;Y.clear();Y.push_back(rt[l-1]);

        while(p) Y.push_back(T[p]),p-=p&-p;

        return Que(1,ncnt,k);

    }

    void Upd(int p,int x,int y){

        while(p<=n) Add(T[p]?T[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,T[p]=++cnt),1,ncnt,x,y),p+=p&-p;

    }

}S;

char opt[N][1];

int main(){

    rep(kase,1,rd()){

        n=rd(),m=rd();

        cnt=0; memset(S.T,0,sizeof S.T);

        rep(i,1,n) a[i]=b[i]=rd();

        ncnt=n;

        rep(i,1,m) {

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

            if(opt[i][0]=='Q'){

                c[i]=rd(),d[i]=rd(),e[i]=rd();

            } else {

                c[i]=rd(),d[i]=rd();

                b[++ncnt]=d[i];

            }

        }

        sort(b+1,b+ncnt+1);ncnt=unique(b+1,b+ncnt+1)-b-1;

        rep(i,1,n) {

            a[i]=lower_bound(b+1,b+ncnt+1,a[i])-b;

            H.Add(rt[i]=++cnt,rt[i-1],1,ncnt,a[i],1);

        }

        rep(i,1,m){

            if(opt[i][0]=='Q'){

                int ans=S.query(c[i],d[i],e[i]);

                printf("%d\n",b[ans]);

            }else {

                d[i]=lower_bound(b+1,b+ncnt+1,d[i])-b;

                S.Upd(c[i],a[c[i]],-1);

                S.Upd(c[i],a[c[i]]=d[i],1);

            }

        }

    }

}

巴特西

Dynamic_Rankings(动态区间第k大)

ZOJ - 2112

最新文章

热门文章