【Codeforces 587F】Duff is Mad

Author Avatar
mrsrz 1月 16, 2020

AC 自动机，根号分治。

题目大意：

给定 $n$ 个字符串 $s_1,s_2,\ldots,s_n$。有多个询问，每次给出 $l,r,k$，要求回答 $s_l,s_{l+1},\ldots,s_r$ 这些字符串在 $s_k$ 中的出现次数的总和。

题解：

最暴力的方法是建 AC 自动机后，每次询问在 AC 自动机上跑，把跑到的点到根路径上的所有在 $l\sim r$ 内的点的个数加起来。

考虑两个比较优的做法。

  • 建 AC 自动机，对每个串 $k$，我们标记它在 AC 自动机上匹配到的位置，并对 fail 树求和。然后一个串在 $s_k$ 中的出现次数，就是这个串结尾的结点的子树大小。然后我们依次把 $1\sim n$ 对 $s_k$ 的贡献加上，得到前缀和数组，就可以处理所有关于 $k$ 的询问。
  • 建 AC 自动机，对询问差分成 $[1,r]-[1,l-1]$ 的形式。我们把 $1\sim n$ 在 AC 自动机上的结尾位置按次序加入（它会对一棵子树产生贡献），加入第 $i$ 个串的贡献后，处理所有 $[1,i]$ 的询问，方法为直接在上面匹配并累加贡献。

这两种方法对于不同的数据有不同的表现。考虑根号分治。

对于 $|s_k|\geq\sqrt n$ 的串 $k$，这样的 $k$ 不超过 $\sqrt n$ 中，我们对每个 $k$，都用方法一求出所有关于 $k$ 的询问的答案，总时间复杂度 $O(n\sqrt n)$。

对于 $|s_k|\lt \sqrt n$ 的串 $k$，它在 AC 自动机上匹配的复杂度为 $O(\sqrt n)$，因此我们对所有 $|s_k|\lt\sqrt n$ 的询问同时用方法二计算，每次暴力在上面匹配。这里涉及到 $O(n)$ 次子树加，$O(n\sqrt n)$ 次单点查询的操作，用一个序列分块平衡两部分复杂度，即可做到 $O(n\sqrt n)$。

总时间复杂度 $O(n\sqrt n)$。

Code：

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
#define bel(x)((x-1)/siz+1)
const int siz=320,N=1e5+5;
char*s[N],ss[N];
queue<int>q;
int n,m,len[N],ch[N][26],fail[N],nod,sz[N],head[N],cnt,ed[N];
LL pre[N],ans[N];
int dfn[N],idx=0,blocks;
struct edge{
    int to,nxt;
}e[N];
struct que{
    int l,r,id;
};
vector<que>qs[N];
vector<pair<int,int> >qt[N];
void insert(char*s,int n,int id){
    int nw=0;
    for(int i=0;i<n;++i){
        const int c=s[i]-'a';
        if(!ch[nw][c])ch[nw][c]=++nod;
        nw=ch[nw][c];
    }
    ed[id]=nw;
}
void build(){
    for(int i=0;i<26;++i)
    if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;++i)if(int v=ch[u][i]){
            fail[v]=ch[fail[u]][i];
            q.push(v);
        }else ch[u][i]=ch[fail[u]][i];
    }
    for(int i=1;i<=nod;++i)
    e[++cnt]=(edge){i,head[fail[i]]},head[fail[i]]=cnt;
}
void DFS(int now){
    for(int i=head[now];i;i=e[i].nxt)DFS(e[i].to),sz[now]+=sz[e[i].to];
}
void ins_(char*s,int n){
    int nw=0;
    for(int i=0;i<n;++i){
        const int c=s[i]-'a';
        nw=ch[nw][c];
        ++sz[nw];
    }
    DFS(0);
}
void work1(){
    for(int i=1;i<=n;++i)
    if(len[i]>=siz&&!qs[i].empty()){
        memset(pre,0,sizeof pre);
        memset(sz,0,sizeof sz);
        ins_(s[i],len[i]);
        for(int i=1;i<=n;++i)
        pre[i]=pre[i-1]+sz[ed[i]];
        vector<que>&vec=qs[i];
        for(int i=0;i<vec.size();++i)
        ans[vec[i].id]=pre[vec[i].r]-pre[vec[i].l-1];
    }
}
void dfs(int now){
    sz[now]=1,dfn[now]=++idx;
    for(int i=head[now];i;i=e[i].nxt)dfs(e[i].to),sz[now]+=sz[e[i].to];
}
int tc[400],ts[N];
inline void add(int l,int r){
    const int bL=bel(l),bR=bel(r);
    if(bL==bR)for(int i=l;i<=r;++i)++ts[i];else{
        for(int i=bL*siz;i>=l;--i)++ts[i];
        for(int i=(bR-1)*siz+1;i<=r;++i)++ts[i];
        for(int i=bL+1;i<bR;++i)++tc[i];
    }
}
inline int ask(int x){return tc[bel(x)]+ts[x];}
int get(char*s,int n){
    int nw=0,ret=0;
    for(int i=0;i<n;++i){
        nw=ch[nw][s[i]-'a'];
        ret+=ask(dfn[nw]);
    }
    return ret;
}
void work2(){
    blocks=bel(n);
    memset(sz,0,sizeof sz);
    dfs(0);
    for(int i=1;i<=n;++i){
        add(dfn[ed[i]],dfn[ed[i]]+sz[ed[i]]-1);
        vector<pair<int,int> >&vec=qt[i];
        for(int i=0;i<vec.size();++i){
            int k=vec[i].first,id=vec[i].second;
            int res=get(s[k],len[k]);
            if(id>0)ans[id]+=res;else ans[-id]-=res;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%s",ss);
        len[i]=strlen(ss);
        s[i]=new char[len[i]+2];
        for(int j=0;j<len[i];++j)s[i][j]=ss[j];
        s[i][len[i]]=0;
        insert(ss,len[i],i);
    }
    build();
    for(int i=1;i<=m;++i){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        if(len[k]>=siz)qs[k].push_back((que){l,r,i});else
        qt[r].push_back(make_pair(k,i)),qt[l-1].push_back(make_pair(k,-i));
    }
    work1();
    work2();
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}
Powered by Hexo
Theme - Material