题解--风雨

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
首先肯定是要建 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;
}