自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:39:49，当前版本为作者最后更新于2022-09-29 14:31:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part1 题意简述：

三个操作：区间按位右移，复制，求和。

$n,m\le3\times10^6,C\le10^9$，$C$ 为值域，以下均同。

Part2 前置知识：

可持久化 WBLT；花神游历各国。

Part3 正题：

如果没有复制操作，就可以暴力右移非零数，复杂度 $O(n\log_2n\log_2C)$，但有复制操作，就会影响势能，时间退化成 $O(nm)$。

使用可持久化平衡树维护复制操作，依旧考虑每一个数最多右移 $\log_2C$ 次，这样可以树上每一个节点存储右移 $[0,\log_2C]\cap Z$ 次的结果，而每一次操作会多出 $O(\log_2n)$ 个节点，这样空间复杂度是 $O(m\log_2n\log_2C)$ 的，不能通过。

如果每隔 $\frac{m}{\log_2n}$ 次操作就搜出所有节点，然后重构，就可以做到空间 $O(n\log_2C)$，但是时间有 $O((n+m)\log_2n\log_2C)$，到这里，如果实现得好一些已经可以通过了。

这里有一个小问题，就是本题给的时间和空间极度不平衡，光建立平衡树就必须 $n\log_2C$ 个 long long，而这样的空间已经达到了 $750MB$,显然开不下。

考虑在建树时底层分块，如果区间长度少于 $\log_2C$，就将整个区间当作一个节点，这样一棵全新的树空间是 $O(n)$ 的。

一棵可爱的 $\text{WBLT}$：

ul sm[M][33],ans;
D n,q,a[N],t[M][2];
#define ls t[x][0]
#define rs t[x][1]
D g[M],cnt,F[M],ft;
D sz[M],L[M],b[N],rt;
inline void cp(D &x){
    if(F[x]==ft)return;
    F[++cnt]=ft;L[cnt]=L[x];
    g[cnt]=g[x],sz[cnt]=sz[x];
    t[cnt][0]=ls,t[cnt][1]=rs;
    for(D i=0;i<=30;++i)
        sm[cnt][i]=sm[x][i];
    x=cnt;
}inline void add(D &x,D ta){
    cp(x),g[x]=min(g[x]+ta,30u);
}
inline void pp(D x){
    sz[x]=sz[ls]+sz[rs];
    L[x]=L[ls]+L[rs];
    for(D i=0;i<=30;++i){
        sm[x][i]=0;
        if(i+g[ls]<=30)sm[x][i]+=sm[ls][i+g[ls]];
        if(i+g[rs]<=30)sm[x][i]+=sm[rs][i+g[rs]];
    }
}inline void pd(D &x){
    if(g[x]&&sz[x]>1){
        cp(x),add(ls,g[x]);
        add(rs,g[x]);
        for(D i=30-g[x];~i;--i)
            sm[x][i]=sm[x][i+g[x]];
        for(D i=30-g[x]+1;i<=30;++i)
            sm[x][i]=0;
        g[x]=0;
    }
}
D spt(D x,D l,D r){
    if(!x||l>r)return 0;
    if(l==1&&r==L[x])return x;
    if(sz[x]==1){
        g[++cnt]=g[x],L[cnt]=r-l+1,sz[cnt]=1;
        t[cnt][0]=ls+l-1,t[cnt][1]=ls+r-1;
        F[x=cnt]=ft;D i,j;
        for(i=0;i<=30;++i)
            for(sm[x][i]=0,j=ls;j<=rs;++j)
                sm[x][i]+=a[j]>>i;
        return x;
    }else{
        cp(x),pd(x);
        if(r<=L[ls])return spt(ls,l,r);
        else if(l>L[ls])return spt(rs,l-L[ls],r-L[ls]);
        else{
            rs=spt(rs,1,r-L[ls]),ls=spt(ls,l,L[ls]);
            pp(x);return x;
        }
    }exit(100000);return 1e9;
}
D build(D l,D r){
    D x=++cnt;F[x]=ft,g[x]=0,L[x]=r-l+1;
    if(r-l<30){
        ls=l,rs=r,sz[x]=1;D i,j;
        for(i=0;i<=30;++i)
            for(sm[x][i]=0,j=l;j<=r;++j)
                sm[x][i]+=a[j]>>i;
    }else{
        D md=l+r>>1;ls=build(l,md);
        rs=build(md+1,r);pp(x);
    }return x;
}
void dfs(D x,D dat=0){
    dat=min(dat+g[x],30u);
    if(sz[x]>1){
        dfs(ls,dat),dfs(rs,dat);
    }else{
        for(D i=ls;i<=rs;++i)
            b[++n]=a[i]>>dat;
    }
}
D mg(D L,D R){
    if(!L||!R)return L|R;
    D x=sz[L]>sz[R]?L:R,sm=sz[L]+sz[R];
    if(sz[x]<ra*sm){
        g[x=++cnt]=0,F[x]=ft;
        ls=L,rs=R,pp(x);
        return x;
    }if(x==L){
        cp(x),pd(x);
        if(sz[ls]>af*sm){
            rs=mg(rs,R),pp(x),g[x]=0;
            return x;
        }else{
            D y=rs;cp(y),pd(y);
            return mg(mg(ls,t[y][0]),mg(t[y][1],R));
        }
    }else{
        cp(x),pd(x);
        if(sz[rs]>af*sm){
            ls=mg(L,ls),pp(x),g[x]=0;
            return x;
        }else{
            D y=ls;cp(y),pd(y);
            return mg(mg(L,t[y][0]),mg(t[y][1],rs));
        }
    }exit(1000000);return 1e9;
}

Part4 关于常数

显然在没什么人提交时我一发得到了最优解 $(2022.9.29)$，时间最快 $1.70min$，空间最小 $160MB$，由此可见，常数优秀的 $\text{WBLT}$ 让我们不再需要卡常。时限太变态了，缩到 $30s$ 怎么样？或者把空间放到 $200MB$?不然这就是一个完全不卡常的 $\text{Ynoi}$ 了。

Part5 后记

这篇文章只是抛砖引玉，作者听说有空间线性的做法，以及可以分裂合并的 $\text{AVL}$ 树，希望大家多多分享。