自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

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

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

以下是正文

$\text{Link}$

题意

给出长为 $n$ 的序列 $a,b$，$b$ 序列初始为 $0$，$m$ 次操作，每次给出 $a$ 中的一个区间 $[l,r]$ 与 $L$，执行 $\forall i\in[l,r],b_{i+L-l}\gets b_{i+L-l}+a_i$。

求出所有操作后的 $b$ 序列。

$n\le 10^5$，$m\le10^6$。

思路

乐子一血。

对序列 $a$ 按照块长为 $B$ 分块，对于一次操作，若 $l,r$ 同块，则直接加，否则先对散块暴力，整块存下来暂不处理。

所有询问的散块处理完之后，处理整块。对于每个块 $[bL,bR]$，我们记录 $c_i$ 表示这个块加到 $b$ 序列中以 $i$ 开始的等长区间的次数，$d_i=a_{bL+i}(i\le bR-bL)$。令这个块对 $b_i$ 的贡献为 $res_i$，则有 $\displaystyle res_i=\sum_{j=1}^i c_jd_{i-j}$，可以卷积。

复杂度为 $O(mB+\dfrac{(n\log n+m)n}B)$，取 $B=O(\sqrt\dfrac{n^2\log n+nm}m)$ 得到最优复杂度 $O(n\sqrt{m\log n}+m\sqrt n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=131072,mod=998244353;
namespace Init{
	int fac[N],ifac[N],inv[N],G[17][N];
	inline int qpow(int x,int y){
		int res=1;
		while(y){
			if(y&1) res=1ll*res*x%mod;
			x=1ll*x*x%mod;
			y>>=1;
		}
		return res;
	}
	inline void getG(){
		for(int i=0;i<17;i++){
			int *P=G[i],W=1<<i;
			P[0]=1;
			P[1]=qpow(3,(mod-1)/(1<<i+1));
			const int tmp=P[1];
			for(int j=2;j<W;j++)
				P[j]=1ll*P[j-1]*tmp%mod;
		}
	}
	inline void Prefix(int L){
		fac[0]=1;
		for(int i=1;i<=L;i++)
			fac[i]=1ll*fac[i-1]*i%mod;
		ifac[L]=qpow(fac[L],mod-2);
		for(int i=L;i>=1;i--)
			ifac[i-1]=1ll*ifac[i]*i%mod;
		for(int i=1;i<=L;i++)
			inv[i]=1ll*fac[i]*ifac[i-1]%mod;
	}
}
using namespace Init;
namespace Poly{
    int lim,rev[N];
    int F[N],G[N],H[N];
    inline void init(int n,int mode=1){
        if(mode){
            int l=0;
            for(lim=1;lim<=n;lim<<=1)l++;
            for(int i=1;i<lim;i++)
                rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        }else{
            for(lim=1;lim<=n;lim<<=1);
        }
    }
    inline void NTT(int *a,int T){
        for(int i=0;i<lim;i++)
            if(i<rev[i])
                swap(a[i],a[rev[i]]);
        for(int i=1,o=0;i<lim;i<<=1,o++){
            const int *P=::G[o];
            for(int j=0;j<lim;j+=(i<<1)){
                int t1,t2;
                for(int k=0;k<i;k++){
                    t1=a[j+k];
                    t2=1ll*P[k]*a[i+j+k]%mod;
                    a[j+k]=(t1+t2)%mod;
                    a[i+j+k]=(t1-t2+mod)%mod;
                }
            }
        }
        if(T==1) return ;
        int Inv=qpow(lim,mod-2);
        reverse(a+1,a+lim);
        for(int i=0;i<lim;i++)
            a[i]=1ll*a[i]*Inv%mod;
    }
    inline void Mul(int *a,int *b){
        for(int i=0;i<lim;i++)
            F[i]=b[i];
        NTT(a,1),NTT(F,1);
        for(int i=0;i<lim;i++)
            a[i]=1ll*a[i]*F[i]%mod;
        NTT(a,-1);
    }
}
const int T=1e5+10,Q=1e6+10,sq=sqrt(1.0*T*T*log2(T)/Q+Q)*2;
int n,q,blk,a[T],b[T],c[N],d[N],bel[T],bl[T],br[T];
struct Query{
	int l,bL,bR,L;
}que[Q];
inline void solve(int bL,int bR){
	int D=bel[bL],len=bR-bL+1;
	for(int i=0;i<=Poly::lim;i++)
		c[i]=d[i]=0;
	for(int i=1;i<=q;i++)
		if(que[i].bL<=D&&D<=que[i].bR)
			c[que[i].L+bL-que[i].l]++;
	for(int i=1;i<=len;i++)
		d[i-1]=a[bL+i-1];
	Poly::Mul(c,d);
	for(int i=1;i<=n;i++)
		b[i]+=c[i];
}
int main(){
	n=read();
	getG(),Poly::init(n+2000);
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i+=sq){
		blk++;
		bl[blk]=i,br[blk]=min(i+sq-1,n);
		for(int j=bl[blk];j<=br[blk];j++)
			bel[j]=blk;
	}
	q=read();
	for(int i=1;i<=q;i++){
		int l=read(),r=read(),L=read();
		int bL=bel[l],bR=bel[r];
		if(bL==bR){
			for(int j=l;j<=r;j++)
				b[L+j-l]+=a[j];
		}else{
			for(int j=l;j<=br[bL];j++)
				b[L+j-l]+=a[j];
			for(int j=bl[bR];j<=r;j++)
				b[L+j-l]+=a[j];
			que[i]={l,bL+1,bR-1,L};
		}
	}
	for(int i=1;i<=blk;i++)
		solve(bl[i],br[i]);
	for(int i=1;i<=n;i++)
		write(b[i]),putc('\n');
	flush();
}

再见 qwq~