【XSY4058】区间加区间（分块FFT）

题面

区间加区间

题解

考虑若操作是将 \(a_1,\cdots,a_n\) 加到 \(b_l,\cdots,b_{l+n-1}\)，我们可以记录每个 \(l\) 被操作的次数 \(c_l\)，那么最后的 \(b_i=\sum_{j=1}^n a_jc_{i-j+1}\)，可以直接 FFT 优化到 \(O(n\log n)\)。

但现在是选 \(a\) 中的一段位置加到 \(b\) 中的一段位置，那么直接对 \(a\) 分块即可，然后变成散块单调加和整块加到 \(b\) 中的某一段位置上。假设块长为 \(B\)，那么时间复杂度为 \(O((n\log n+m)(n/B)+mB)=O(\sqrt{nm(n\log n+m)})\)。

#include<bits/stdc++.h>

#define LN 18
#define N 100010
#define M 1000010

using namespace std;

namespace modular
{
	const int mod=1004535809;
	inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
	inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
	inline int mul(int x,int y){return 1ll*x*y%mod;}
	inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
	inline void Dec(int &x,int y){x=x-y<0?x-y+mod:x-y;}
	inline void Mul(int &x,int y){x=1ll*x*y%mod;}
}using namespace modular;

inline int poww(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

vector<int> w[LN][2];

void init(int limit)
{
	for(int bit=0,mid=1;mid<limit;bit++,mid<<=1)
	{
		int len=mid<<1;
		int gn=poww(3,(mod-1)/len);
		int ign=poww(gn,mod-2);
		int g=1,ig=1;
		for(int j=0;j<mid;j++,Mul(g,gn),Mul(ig,ign))
			w[bit][0].push_back(g),w[bit][1].push_back(ig);
	}
}

void NTT(int *a,int limit,int opt)
{
	static int rev[N<<1];
	opt=(opt<0);
	for(int i=0;i<limit;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)*(limit>>1));
	for(int i=0;i<limit;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int bit=0,mid=1;mid<limit;bit++,mid<<=1)
	{
		for(int i=0,len=mid<<1;i<limit;i+=len)
		{
			for(int j=0;j<mid;j++)
			{
				int x=a[i+j],y=mul(w[bit][opt][j],a[i+mid+j]);
				a[i+j]=add(x,y),a[i+mid+j]=dec(x,y);
			}
		}
	}
	if(opt)
	{
		int tmp=poww(limit,mod-2);
		for(int i=0;i<limit;i++) Mul(a[i],tmp);
	}
}

typedef vector<int> poly;

poly Mul(const poly &a,const poly &b)
{
	static int A[N<<1],B[N<<1];
	const int sa=a.size(),sb=b.size();
	for(int i=0;i<sa;i++) A[i]=a[i];
	for(int i=0;i<sb;i++) B[i]=b[i];
	int limit=1;
	while(limit<(sa+sb-1)) limit<<=1;
	NTT(A,limit,1),NTT(B,limit,1);
	for(int i=0;i<limit;i++) Mul(A[i],B[i]);
	NTT(A,limit,-1);
	poly c(sa+sb-1);
	for(int i=0;i<sa+sb-1;i++) c[i]=A[i];
	for(int i=0;i<limit;i++) A[i]=B[i]=0;
	return c;
}

const int B=2000;

struct data
{
	int l,r,L;
}q[M];

int n,m,a[N],b[N],block[N];

void solve(int id)
{
	poly c(n-B+2);
	int bl=(id-1)*B+1;
	for(int i=1;i<=m;i++)
		if(block[q[i].l]<id&&id<block[q[i].r])
			c[q[i].L+bl-q[i].l]++;
	poly aa(B+1);
	for(int i=1;i<=B;i++) aa[i]=a[bl+i-1];
	poly res=Mul(c,aa);
	for(int i=2;i<=n+1;i++) b[i-1]+=res[i];
}

int main()
{
	n=read();
	int limit=1;
	while(limit<=n+3) limit<<=1;
	init(limit);
	for(int i=1;i<=n;i++)
		a[i]=read(),block[i]=(i-1)/B+1;
	m=read();
	for(int i=1;i<=m;i++)
	{
		int l=read(),r=read(),L=read();
		q[i].l=l,q[i].r=r,q[i].L=L;
		int bl=block[l],br=block[r];
		if(bl==br)
		{
			for(int j=l;j<=r;j++) b[L+j-l]+=a[j];
			continue;
		}
		for(int j=l,t=bl*B;j<=t;j++) b[L+j-l]+=a[j];
		for(int j=(br-1)*B+1;j<=r;j++) b[L+j-l]+=a[j];
	}
	int nB=block[n];
	for(int i=2;i<nB;i++) solve(i);
	for(int i=1;i<=n;i++) printf("%d\n",b[i]);
	return 0;
}
/*
3
1 2 3
1 
1 2 2
*/