自动搬运

查看原文

来自洛谷，原作者为

	Binary_Search_Tree 博客 https://cnblogs.com/bestlxm

搬运于2025-08-24 22:14:39，当前版本为作者最后更新于2019-12-18 23:13:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：给出两个序列$T,P$ 动态修改、询问$\sum\limits_{i=0}^{l-1}(A[i+x]-B[i])^2$的值

$\sum\limits_{i=0}^{l-1}(A[i+x]-B[i])^2=\sum\limits_{i=0}^{l-1}A[i+x]^2+B[i]^2-2A[i+x][Bi]$

如果没有修改操作，翻转A数组或B数组后就是裸的FFT了

• 如果每次操作都暴力修改+FFT时间复杂度显然爆炸

• 如果每次操作都不修改，记下修改序列，询问时加上修改序列的贡献，复杂度仍然爆炸

于是考虑把两种方法结合起来，对操作序列分块

设块的大小为$B$，则做一个块的时间复杂度为$O(S^2+n\log n)$ 总复杂度为$O(mS+\frac{nm\log n}{S})$

$mS=\frac{nm\log n}{S}$即$S=\sqrt{n\log n}$时，复杂度取最小值$O(m\sqrt{nlogn})$

虽然看上去复杂度很大，但是有4s的时限，出题人也友善地提供了各种优化开关。

所以应该是可以过哒~

附代码（有少量卡常):

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define M 1000005
#define mod 998244353
#define g 3
using namespace std;
int n,ll,m,len=1,L,power3[M],power_inv3[M],rev[M],H,cnt;
int X[M],Y[M],E[M];
long long A[M],B[M],C[M],tmp_A[M],tmp_B[M],len_inv,sum;
long long add(long long u,long long v){return (u+=v)>=mod?u-mod:u;}
long long inv(long long x){return x==1?1:(mod-mod/x)*inv(mod%x)%mod;}
long long power(long long x,long long y){
	long long ans=1,now=x;
	for (register long long i=y;i;i>>=1,now=now*now%mod)
		if (i&1) ans=ans*now%mod;
	return ans;
}
char get_char(){//快读（字母）
	char c=getchar();
	while (c<'a'||c>'z') c=getchar();
	return c-'a';
}
int read(){//快读（整数)
	char c=getchar();int ans=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
	return ans;
}
void Write(long long x){//快速输出
	if (x<10) putchar(x^48);
	else Write(x/10),putchar((x%10)^48);
	return;
}
void NTT(long long *A,int flag){//NTT板子
	for (register int i=0;i<len;i++)
		if (i<rev[i]) swap(A[i],A[rev[i]]);
	for (register int l=1;l<len;l<<=1){
		long long T=(flag==1?power3[l]:power_inv3[l]);
		for (register int i=0;i<len;i+=(l<<1)){
			long long t=1;
			for (register int j=0;j<l;j++,t=t*T%mod){
				long long u=A[i+j],v=A[i+j+l]*t%mod;
				A[i+j]=add(u,v),A[i+j+l]=add(u,mod-v);
			}
		}
	}
	return;
}
void mul(){//多项式乘法
	for (register int i=0;i<len;i++) tmp_B[i]=B[i];NTT(tmp_B,1);
	for (register int i=0;i<len;i++) C[i]=tmp_A[i]*tmp_B[i]%mod;NTT(C,-1);
	for (register int i=0;i<len;i++) C[i]=C[i]*len_inv%mod;
	return;
}
long long query(int x){//处理询问操作
	long long now=C[x+ll-1];x+=ll-1;
	for (register int i=1;i<=X[0];i++) now+=Y[i]*A[x-X[i]];//暴力加上修改块内修改操作贡献
	return sum+E[x]-(x>=ll?E[x-ll]:0)-now*2;
}
int main(){
	n=read(),ll=read(),m=read();H=(int)(pow(n*log2(n),0.5))*3;
	while (len<=n+ll) len<<=1,++L;
	for (register int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);
	for (register int i=0;i<n;i++) tmp_A[i]=A[i]=get_char(),E[i]=E[i-1]+A[i]*A[i];
	for (register int i=0;i<ll;i++) B[i]=get_char(),sum+=B[i]*B[i];
	for (register int i=0,j=ll-1;i<j;i++,j--) swap(B[i],B[j]);
	for (register int l=1;l<len;l<<=1) 
		power3[l]=power(g,(mod-1)/(l<<1)),power_inv3[l]=power(inv(g),(mod-1)/(l<<1));
	len_inv=inv(len);NTT(tmp_A,1);mul();//对密码串T只需要做一次FFT
	for (register int i=1,opt;i<=m;i++){
		opt=read();
		if (opt==1) Write(query(read()-1)),putchar('\n');
		else {
			X[++X[0]]=ll-read(),Y[++Y[0]]=get_char();
			sum-=B[X[X[0]]]*B[X[X[0]]];
			int tmp=B[X[X[0]]];B[X[X[0]]]=Y[Y[0]],Y[Y[0]]-=tmp;
			sum+=B[X[X[0]]]*B[X[X[0]]];
		}
		if (X[0]==H) mul(),X[0]=Y[0]=0;//块的末尾暴力做NTT
	}
	return 0;
}

看完求赞~