题解 CF1207G Indie Album

· · 题解

CF1207G Indie Album

题意简述：有 n 种操作，给出整数，整数和字符 op,j(op=2),c。若 op=1 则 s_i=c；否则 s_i=s_j+c。m 次询问给出 i,t，求 t 在 s_i 中的出现次数。

本文节选自 ACAM 乱做 IV.

以前打过这场比赛，要是我当时会 ACAM 多好啊。

注意到如果我们对操作串 s 建出 ACAM 需要动态修改 fail 树的结构，不太可行。那么换个思路，考虑对所有询问串 t 建出 ACAM。那么这样就是在 ACAM 上跑 s_i，求出有多少个跑到的节点在 fail 树上以 t 的终止节点的子树中。这个可以对 fail 树进行一遍 dfs，用每个节点的 dfs 序和 size 维护。这样就是单点修改，区间查询，用树状数组即可。

可是 s_i 的总长度可能会很大。不难发现每个 s_i 形成了一个依赖关系，建出树，我们只需要再对这个 “操作树” 进行 dfs，先计算贡献（位置 son_{p,c_i} 加上 1），再更新并下传跑到的位置 p=son_{p,c_i}，最后撤销贡献即可。

时间复杂度 \mathcal{O}((n+m)\log \sum|t|)。 

/*
    Powered by C++11.
    Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize(3)
//#define int long long

#define pb emplace_back

const int N=4e5+5;

int n,m,ans[N];
int cnt,dn,son[N][26],ed[N],fa[N],sz[N],dfn[N];
vector <int> e[N],f[N],ft[N];
char ad[N];
void ins(int id,string s){
    int p=0;
    for(char it:s){
        if(!son[p][it-'a'])son[p][it-'a']=++cnt;
        p=son[p][it-'a'];
    } ed[id]=p;
} void build(){
    queue <int> q;
    for(int i=0;i<26;i++)if(son[0][i])q.push(son[0][i]);
    while(!q.empty()){
        int t=q.front(); q.pop();
        for(int i=0;i<26;i++)
            if(son[t][i])q.push(son[t][i]),fa[son[t][i]]=son[fa[t]][i];
            else son[t][i]=son[fa[t]][i];
        ft[fa[t]].pb(t);
    }
} void dfs(int id){
    dfn[id]=++dn,sz[id]=1;
    for(int it:ft[id])dfs(it),sz[id]+=sz[it];
}

int c[N];
void add(int x,int v){while(x<=dn)c[x]+=v,x+=x&-x;}
int query(int x){int ans=0; while(x)ans+=c[x],x-=x&-x; return ans;}
int query(int l,int r){return query(r)-query(l-1);}
void cal(int id,int p){
    if(id)p=son[p][ad[id]-'a'],add(dfn[p],1);
    for(int it:e[id])ans[it]=query(dfn[ed[it]],dfn[ed[it]]+sz[ed[it]]-1);
    for(int it:f[id])cal(it,p);
    add(dfn[p],-1);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int tp,p=0; cin>>tp;
        if(tp==2)cin>>p;
        f[p].pb(i),cin>>ad[i];
    } cin>>m;
    string q;
    for(int i=1,id;i<=m;i++)
        cin>>id>>q,e[id].pb(i),ins(i,q);
    build(),dfs(0),cal(0,0);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}