LGP7582题解

他说风雨中这点痛算什么，擦干泪不要怕，至少我们还有梦

首先弄明白一件事：区间 ACAM 可以看做是所有串的 ACAM 只保留区间串对节点贡献的信息，仍然可以使用所有串的 ACAM 的转移边。

于是我们可以使用 ACAM 套线段树，每颗线段树维护这个节点会受到区间哪些位置的串的贡献。

但是这这样有一个问题，修改操作不太容易实现。

那么我们还需要再套一层数据结构来解决这个修改。区间询问一般考虑线段树和分块。线段树的话修改操作会涉及过多的节点，所以我们选择分块。

设块长为 \(B\)。对每个块的 ACAM 维护两种类型的值：\(V[u]\) 表示不计算整体加 \(tag\) 的权值之和，\(c[u]\) 表示这个节点包含的串的个数。

对于整块，区间加操作就直接加，如果是赋值那就清空 \(V\) 然后令 \(tag\) 等于赋的值。

我们是很容易通过这两个数组来计算一个节点的权值的。对于整块我们可以这样做到 \(O(\sum|S|\frac{n}{B})\) 个询问操作。

散块的修改操作需要暴力进行，涉及到的 ACAM 节点个数是 \(O(\sum|s|)\) 级别的。不过可以知道需要修改的 ACAM 节点是 \(O(B)\) 个。所以修改操作是 \(O(mB)\) 个。

但是询问就比较麻烦了。前面提到可以将区间 ACAM 看做是所有串的 ACAM 只保留区间串对节点贡献的信息，所以对于每个块的 ACAM 都套上一颗线段树，维护哪些串贡献这个节点。

但是查询的时候只能暴力把这个集合弄出来一个一个加。不过由于加的是字符串的信息所以是 \(O(1)\) 维护的。

查询散块的复杂度为 \(O(\sum|S|B)\)。

注意到前面的询问次数过多，线段树这种东西是不能胜任的，考虑对 dfn 序分块。

每次修改相当于子树加，也就是区间加。我们将 fail 树的 dfn 序分成块长为 \(T\) 的块。每次修改暴力加后缀，然后 \(O(B)\) 次操作结束后进行一个块的前缀和。

那么就是 \(O(\sum|S|\frac{n}{B}+mBT+\frac{\sum|S|m}{T})\)，\(T\) 取 \(\sqrt{\frac{\sum|S|}{B}}\) 可以得到 \(O(\sum|S|\frac{n}{B}+m\sqrt{\frac{\sum|S|}{B}})\) 的复杂度。

\(B\) 取 \(\sqrt{n}\) 即可得到 \(O(\sum|S|\sqrt{n}+\frac{m}{\sqrt[4]{n}}\sqrt{\sum|S|})\) 的复杂度。

线段树合并的话，序列长度其实只有 \(\lfloor\sqrt{30000}\rfloor=173\)，这玩意儿还不如去用 bitset。空间几乎是线性的，不会被卡。

补充：bitset 部分的时间和空间都是 \(O(\sum|S|\frac{\sqrt{n}}{w})\)。

#include
#include
#include
#include
typedef long long ll;
const int M=2e5+5;
int n,m,B,P,tot,a[M];char S[M],T[M],*s[M],*t[M];int lens[M],lent[M];
int sums,sumt;int L[M],R[M],pos[M];int opt[M],l[M],r[M],k[M];
namespace Solve{
	int dfc,V[M],c[M],l[M],r[M],pos[M],fail[M],trans[M][3];std::bitset<180>bit[M];
	int _s[M<<1],_tim[M<<1],_S[M<<1];int _pos[M<<1],_L[M<<1],_R[M<<1];
	int*ns=_s,*ntim=_tim,*nS=_S,*npos=_pos,*nL=_L,*nR=_R;
	int cnt,h[M];
	struct Edge{
		int v,nx;
	}e[M];
	inline void Add(const int&u,const int&v){
		e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
	}
	inline int Insert(int u,char*s,const int&v,const int&n){
		for(int i=0;in)R[i]=n;
				}
			}
			inline void Add(int x,const int&V){
				for(int i=x;i<=R[x];++i){
					if(tim[i]^T)tim[i]=T,s[i]=0;s[i]+=V;
				}
			}
			inline void update(){
				for(int i=1;i<=pos[n];++i){
					if(tim[R[(i-1)*B+1]]^T)tim[R[(i-1)*B+1]]=T,s[R[(i-1)*B+1]]=0;S[i]=S[i-1]+s[R[(i-1)*B+1]];
				}
				typ=false;
			}
			inline int Qry(const int&x){
				if(tim[x]^T)tim[x]=T,s[x]=0;return typ?0:S[pos[x]-1]+s[x];
			}
			inline void Clear(){
				++T;
			}
		}block;
		inline void Build(const int&L,const int&R){
			for(int i=L;i<=R;++i)a[i-L+1]=::a[i],bit[end[i-L+1]=Insert(rt,::s[i],a[i-L+1],lens[i])][i-L+1]=1;
		}
		inline void init(const int&n){
			block.B=ceil(sqrt(sumt/B));block.init(m);
			for(int i=1;i<=n;++i)block.Add(l[end[i]],a[i]),block.Add(r[end[i]]+1,-a[i]);block.update();
		}
		inline void Add(const int&V){
			tag+=V;
		}
		inline void Cover(const int&V){
			block.Clear();++T;tag=V;block.typ=true;
		}
		inline void Add(const int&V,const int&L,const int&R){
			for(int i=L;i<=R;++i){
				if(tim[i]^T)tim[i]=T,a[i]=0;
				block.Add(l[end[i]],V);block.Add(r[end[i]]+1,-V);a[i]+=V;
			}
			block.update();
		}
		inline void Cover(const int&V,const int&L,const int&R){
			for(int i=L;i<=R;++i){
				if(tim[i]^T)tim[i]=T,a[i]=0;
				block.Add(l[end[i]],V-a[i]-tag);block.Add(r[end[i]]+1,-(V-a[i]-tag));a[i]=V-tag;
			}
			block.update();
		}
		inline ll Qry(char*s,const int&n){
			int u(rt);ll ans(0);
			for(int i=0;in)R[i]=n;
	}
	for(int i=1;i<=P;++i)Solve::block[i].rt=++tot,Solve::pos[i]=i;
	for(int i=1;i<=P;++i)Solve::block[i].Build(L[(i-1)*B+1],R[(i-1)*B+1]);Solve::Build();
	for(int i=1;i<=P;++i)Solve::block[i].init(R[(i-1)*B+1]-L[(i-1)*B+1]+1);
	for(int i=1;i<=m;++i){
		const int&l=::l[i],&r=::r[i],&k=::k[i];
		if(opt[i]==1){
			const int&q=pos[l],&p=pos[r];
			if(q==p)Solve::block[q].Add(k,l-L[l]+1,r-L[r]+1);
			else{
				Solve::block[q].Add(k,l-L[l]+1,R[l]-L[l]+1);Solve::block[p].Add(k,1,r-L[r]+1);
				for(int i=q+1;i<=p-1;++i)Solve::block[i].Add(k);
			}
		}
		if(opt[i]==2){
			const int&q=pos[l],&p=pos[r];
			if(q==p)Solve::block[q].Cover(k,l-L[l]+1,r-L[r]+1);
			else{
				Solve::block[q].Cover(k,l-L[l]+1,R[l]-L[l]+1);Solve::block[p].Cover(k,1,r-L[r]+1);
				for(int i=q+1;i<=p-1;++i)Solve::block[i].Cover(k);
			}
		}
		if(opt[i]==3){
			const int&q=pos[l],&p=pos[r];
			const int&len=lent[i];char*t=::t[i];
			if(q==p)printf("%lld\n",Solve::block[q].Qry(t,len,l-L[l]+1,r-L[l]+1));
			else{
				ll ans=Solve::block[q].Qry(t,len,l-L[l]+1,R[l]-L[l]+1)+Solve::block[p].Qry(t,len,1,r-L[r]+1);
				for(int i=q+1;i<=p-1;++i)ans+=Solve::block[i].Qry(t,len);
				printf("%lld\n",ans);
			}
		}
	}
}