题解--风雨
abruce
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](https://www.luogu.com.cn/problem/CF163E)
首先肯定是要建 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)$，代码细节比较多，有点长，写的时候注意。
```cpp
#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;
}
```