自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:31:15，当前版本为作者最后更新于2021-04-06 08:42:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

感觉 AC 自动机可以出很毒瘤的数据结构题啊，可是为什么没人出啊。/kk
难度和码量大致相当于一个比较简单的 Ynoi 吧。

20pts

直接暴力维护 $a_i$，暴力 KMP 即可。

40pts

线段树上每个节点开一个 AC 自动机，然后统计出现次数就可以了，时间复杂度 $O(nlogn)\sim O(nlog^2n)$。

60pts

似乎可以用 ODT 维护权值，然后将问题转化为区间内字符串在大串出现次数，线段树即可。注意上一个部分分不能用这种方法。

100pts

前置知识：e-Government
首先肯定是要建 AC 自动机的。区间加，区间推平，线段树？可是这个怎么 pushup 啊。我们想到另一种支持区间加，区间推平的数据结构——分块。让我们看分块怎么支持以上的操作。
首先，我们每 $\sqrt{n}$ 个串建一个 AC 自动机，同时建出它的 fail 树。对于初始的 $a_i$ 我们像 e-Government 那样用一个树状数组进行子树加，单点查询。这样，我们在边角修改的时候也可以对树状数组进行操作。
对于整块的修改，我们需要多记录一个 $tag$ 数组和一个 $dlt$ 数组。区间整块推平时，我们将 $dlt$ 数组修改为那个值，同时将 $tag$ 置为 $1$，代表这个区间已经被推平。区间加的时候，我们只需要对 $dlt$ 进行操作即可。
在查询的时候，我们对于边角，直接暴力 KMP 即可。对于整块，我们分成两种情况产生贡献。
如果这个区间 $tag$ 为 $1$，我们只需要查询这个块的所有串的出现次数和乘上 $dlt$ 即可。如果 $tag$ 为 $0$，则不仅需要查询这个块的所有串的出现次数和乘上 $dlt$，还需要在树状数组中进行查询。
设字符串总长度为 $L$，则总时间复杂度 $O(L\sqrt{n}\log L)$，代码细节比较多，有点长，写的时候注意。

#include<bits/stdc++.h>
#define addtag(i,k) a[i]+=k,add(l[bj[i]],k),add(r[bj[i]]+1,-k)//给 i 的贡献加上 k
#define chtag(i,k) add(l[bj[i]],k-a[i]),add(r[bj[i]]+1,a[i]-k),a[i]=k//将 i 的贡献改为 k
using namespace std;
typedef long long ll;
inline int read() {
	int __x=0,__f=1;
	char __c=getchar();
	while(__c<'0'||__c>'9') {
		if(__c=='-')__f=-1;
		__c=getchar();
	}
	while(__c>='0'&&__c<='9') {
		__x=__x*10+__c-'0';
		__c=getchar();
	}
	return __x*__f;
}
inline void write(ll __x) {
	if(__x<0) {
		putchar('-');
		__x=-__x;
	}
	if(__x>=10)write(__x/10);
	putchar(__x%10+'0');
}
inline string readstr() {
	char __ch=getchar();
	string __st1="";
	while (__ch<'0'||__ch>'z')
		__ch=getchar();
	while (__ch>='0'&&__ch<='z')
		__st1+=__ch,__ch=getchar();
	return __st1;
}
const int maxn=2e5+5,mod=1e9+7;
struct edge {
	int next,to;
} e[maxn*2];
int t[maxn][3],fail[maxn],h[maxn],v[maxn],dlt[maxn],bj[maxn],l[maxn],r[maxn],bel[maxn],n,m,cnt,tot,pos,rt[maxn],lb[maxn],rb[maxn],nxt[maxn],sqrtn,sn;
ll c[maxn],a[maxn],tag[maxn];
string s[maxn];
queue<int> q;
void addedge(int x,int y) {
	e[++cnt].next=h[x];
	e[cnt].to=y;
	h[x]=cnt;
}
void insert(const string &s,int rot,int u) {
	int root=rot,len=s.length(),y;//插入以 rot 为根的 Trie 中
	for(register int i=0; i<len; i++) {
		y=s[i]-'a';
		if(!t[root][y]) {
			t[root][y]=++tot;
		}
		root=t[root][y];
	}
	v[root]++;
	bj[u]=root;
}
void getfail(int rot) {
	for(register int i=0; i<3; i++) {
		t[0][i]=rot;
	}
	q.push(rot);
	while(!q.empty()) {
		int u=q.front(),f=fail[u];
		q.pop();
		v[u]+=v[f];
		for(register int i=0; i<3; i++) {
			int j=t[u][i];
			if(!j) {
				t[u][i]=t[f][i];
				continue;
			}
			fail[j]=t[f][i];
			q.push(j);
		}
	}
}//构建 Trie 图
void dfs(int u) {
	l[u]=++pos;
	for(register int i=h[u]; i; i=e[i].next) {
		int j=e[i].to;
		dfs(j);
	}
	r[u]=pos;
}
void add(int x,int v) {
	while(x<=pos)c[x]+=v,x+=x&(-x);
}
ll ask(int x) {
	ll sum=0;
	while(x)sum+=c[x],x-=x&(-x);
	return sum;//答案需要开 long long
}
void clrtag(int w) {
	int v;
	for(register int i=lb[w]; i<=rb[w]; i++)v=0,tag[w]?v=dlt[w]:v=a[i]+dlt[w],chtag(i,v);//将这个区间的 dlt 清空，以便维护出 a_i 的真实值
	dlt[w]=tag[w]=0;
}
void add(int lx,int ry,int k) {
	int x=bel[lx],y=bel[ry],v;
	if(x==y) {
		if(tag[x])clrtag(x);
		for(register int i=lx; i<=ry; i++)addtag(i,k);
		return;
	}
	if(tag[x])clrtag(x);
	for(register int i=lx; i<=rb[x]; i++)addtag(i,k);
	if(tag[y])clrtag(y);
	for(register int i=lb[y]; i<=ry; i++)addtag(i,k);
	for(register int i=x+1; i<=y-1; i++)dlt[i]+=k;
}
void change(int lx,int ry,int k) {
	int x=bel[lx],y=bel[ry],v;
	if(x==y) {
		if(dlt[x])clrtag(x);
		for(register int i=lx; i<=ry; i++)chtag(i,k);
		return;
	}
	if(dlt[x])clrtag(x);
	for(register int i=lx; i<=rb[x]; i++)chtag(i,k);
	if(dlt[y])clrtag(y);
	for(register int i=lb[y]; i<=ry; i++)chtag(i,k);
	for(register int i=x+1; i<=y-1; i++)dlt[i]=k,tag[i]=1;
}
ll getkmp(string s,string t) {
	s=' '+s,t=' '+t;
	ll sum=0;
	nxt[1]=0;
	int n=s.length()-1,m=t.length()-1;
	for(register int i=2,j=0; i<=n; i++) {
		while(j>0&&s[i]!=s[j+1]) {
			j=nxt[j];
		}
		if(s[i]==s[j+1])j++;
		nxt[i]=j;
	}
	for(register int i=1,j=0; i<=m; i++) {
		while(j>0&&(j==n||t[i]!=s[j+1]))j=nxt[j];
		if(t[i]==s[j+1])j++;
		sum+=j==n;
	}
	return sum;
}
ll query(int lx,int ry,const string &st) {
	int x=bel[lx],y=bel[ry];
	ll ans=0;
	if(x==y) {
		for(register int i=lx; i<=ry; i++)if(s[i].length()<=st.length())ans+=getkmp(s[i],st)*(tag[x]?dlt[x]:a[i]+dlt[x]);
		return ans;
	}
	for(register int i=lx; i<=rb[x]; i++)if(s[i].length()<=st.length())ans+=getkmp(s[i],st)*(tag[x]?dlt[x]:a[i]+dlt[x]);
	for(register int i=lb[y]; i<=ry; i++)if(s[i].length()<=st.length())ans+=getkmp(s[i],st)*(tag[y]?dlt[y]:a[i]+dlt[y]);//注意此处必须先判谁的长度更长，否则复杂度会退化
	for(register int i=x+1; i<=y-1; i++) {
		int u=rt[i],len=st.length();
		for(register int j=0; j<len; j++) {
			u=t[u][st[j]-'a'];
			ans+=dlt[i]*v[u]+(!tag[i])*ask(l[u]);//在没有 tag 的情况下才在树状数组查询
		}
	}
	return ans;
}
int main() {
	int op,x,y,z;
	string st;
	n=read(),m=read();
	sqrtn=int(sqrt(n));
	sn=n/sqrtn+(n%sqrtn!=0);
	for(register int i=1; i<=sn; i++)lb[i]=(i-1)*sqrtn+1,rb[i]=min(i*sqrtn,n),rt[i]=++tot;
	for(register int i=1; i<=n; i++)bel[i]=(i-1)/sqrtn+1;
	for(register int i=1; i<=n; i++)s[i]=readstr(),a[i]=read(),insert(s[i],rt[bel[i]],i);
	for(register int i=1; i<=sn; i++)getfail(rt[i]);
	for(register int i=1; i<=tot; i++)addedge(fail[i],i);
	for(register int i=1; i<=sn; i++)dfs(rt[i]);
	for(register int i=1; i<=n; i++)add(l[bj[i]],a[i]),add(r[bj[i]]+1,-a[i]);//初始需要插入a_i
	while(m--) {
		op=read(),x=read(),y=read();
		switch(op) {
			case 1: {
				z=read(),add(x,y,z);
				break;
			}
			case 2: {
				z=read(),change(x,y,z);
				break;
			}
			case 3: {
				st=readstr(),write(query(x,y,st)),putchar('\n');
				break;
			}
		}
	}
	return 0;
}