P5840 Divljak 题解

· · 题解

一.题意简述

二.解题方法

字符串的多模式匹配问题，一般用 AC 自动机解决。熟悉 AC 自动机的童鞋应该知道，我们可以对所有的 S 串和 T 串建立 AC 自动机。

  1. 对于每次新加入 P_i 串，我们就对其在 trie 图上对应的所有节点上都加上（不是染上）一个颜色编号为 i。
  2. 对于每次询问 S_x，即为查询在 fail 树上，以串 S_x 的终止节点为根的子树内部有多少种不同的颜色。

那么问题来了：因为一个串 S_x 若在某个串 P_i 中出现了多次，那么应该只统计一次，而树状数组是无法维护“若出现多次则只统计一次”的操作的。

怎么解决呢？需要换一个思路，我们在每个 fail 树的节点上开一棵线段树来维护子树的信息。具体来说，对于一个线段树的一个底层节点，若它的下标为 i，那么他就表示在这棵子树中是否存在串 P_i 在 trie 图上对应的某个节点，存在即为 1，不存在即为 0。那么对于每个询问，就是在某一个节点对应的线段树上求前缀和。

如何维护这么多棵线段树？可以用线段树合并。首先，在每个节点对应的线段树上加上经过这个节点的所有字符串 P_i 所对应的编号，然后递归计算儿子节点，最后将儿子节点的线段树合并上来。底层节点合并的逻辑运算符应该是“或”而不是运算符“加”，这样就能保证出现多次的串只统计一次了。

merge 函数的代码：( val 数组维护区间和，bin 收集废弃节点） 

int merge(int x,int y,int l,int r){
    if(!x || !y) return x|y;
    if(l==r){
        val[x]=val[x]|val[y];
        bin.push_back(y);
        ls[y]=val[y]=rs[y]=0;
        return x;
    }
    int mid=l+r>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    bin.push_back(y);ls[y]=rs[y]=val[y]=0;
    val[x]=val[ls[x]]+val[rs[x]];
    return x;
}

时间复杂度和空间复杂度均为线性对数。但是本题卡线段树合并做法的空间卡的很厉害，所以下面写一下本人使用的常数优化技巧：

1.把所有 STL 容器都删了，尽量手写，实测 vector 额外占用极多空间，当时间卡的不紧的时候用链式前向星代替 vector 存图；

2.注意，线段树合并有两大类型，需要区分。

第一种，无需对每棵线段树都正确维护它的信息，最终的答案在树形结构的根节点上查询就可以了，那么这种情况下，当我们合并线段树节点 x 和 y 时，直接修改 x 的信息（区间和，左儿子，右儿子）即可。

第二种，需要对每棵线段树都正确维护它的信息，查询时每棵线段树都可能用到，那么在每次合并的时候必须新开一个节点 z 表示合并之后的节点，若是直接用 x 的话会造成信息的混乱。

这道题看上去是第二种线段树合并，而这种线段树合并显然是更浪费空间的，那么怎么把它转化成第一种呢？我们可以先读入所有询问，在每个询问所对应的 S_x 终止节点上挂上这个询问，然后在递归进行线段树合并的时候顺便回答掉挂在这个节点上的所有询问，这样的话，这个节点的信息在之后被莫名修改掉也就是一件可以接受的事情了。实际上去掉每次新开节点 z 的空间消耗，可以减小近一半的空间常数。

另外，对于第一种线段树合并，容易发现节点 y 实际上已经没有任何作用，我们可以在废弃它之后将它扔到垃圾桶里并清空它保存的信息。以后需要新开节点的时候，先检查有没有废弃掉的节点，没有的话再新申请。实测这也可以大大减小空间消耗量。

在加上以上种种常数优化之后，我们终于可以通过本题了。感谢毒瘤出题人。

三.代码

#include <bits/stdc++.h>
using namespace std;
const int N=4e6+5,M=3.2e7+5;
int tr[N][26];
int n,q,fail[N],tot=0,R=0,root[N];
int sum=0,ls[M],rs[M],val[M],ed[100005],Ans[100005];
int head[N],nxt[N],ver[N],gg=0;
int vhead[N],vnxt[N],vver[N],gv=0;
int ghead[N],gnxt[100005],gver[100005],gk=0;
vector<int>bin;
char s[N/2];
int New(){
    int u=bin.size(),v;
    if(u){
        v=bin[u-1];
        bin.pop_back();
        return v;
    }
    return ++sum;
}
void add(int x,int y){
    ++gg,nxt[gg]=head[x],head[x]=gg;
    ver[gg]=y;
    return ;
}
void addv(int x,int y){
    ++gv,vnxt[gv]=vhead[x],vhead[x]=gv;
    vver[gv]=y;
    return ;
}
void addg(int x,int y){
    ++gk,gnxt[gk]=ghead[x],ghead[x]=gk;
    gver[gk]=y;
    return ;
}
void insert(int id){
    int now=0,r=0,l=strlen(s),u;
    while(r<l){
        u=(int)(s[r]-'a');
        if(!tr[now][u]) tr[now][u]=++tot;
        now=tr[now][u],++r;
        if(id>0) addv(now,id);
    }
    if(id<0) ed[-id]=now;
    return ;
}
void build(){
    queue<int>q;
    for(int i=0;i<26;++i) if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;++i){
            if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
            else tr[u][i]=tr[fail[u]][i];
        }
    }
    return ;
}
int modify(int x,int l,int r,int y){
    if(!x) x=New();
    if(l==r){val[x]=1;return x;}
    int mid=l+r>>1;
    if(y<=mid) ls[x]=modify(ls[x],l,mid,y);
    else rs[x]=modify(rs[x],mid+1,r,y);
    val[x]=val[ls[x]]+val[rs[x]];
    return x;
}
int merge(int x,int y,int l,int r){
    if(!x || !y) return x|y;
    if(l==r){val[x]=val[x]|val[y];bin.push_back(y);ls[y]=val[y]=rs[y]=0;return x;}
    int mid=l+r>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    bin.push_back(y);ls[y]=rs[y]=val[y]=0;
    val[x]=val[ls[x]]+val[rs[x]];
    return x;
}
int ask(int x,int l,int r,int L,int R){
    if(L>R || !x) return 0;
    if(l==L && r==R) return val[x];
    int mid=l+r>>1;
    if(R<=mid) return ask(ls[x],l,mid,L,R);
    else if(L>=mid+1) return ask(rs[x],mid+1,r,L,R);
    return ask(ls[x],l,mid,L,mid)+ask(rs[x],mid+1,r,mid+1,R);
}
int q2[100005];
void dfs(int x){
    for(int i=vhead[x];i;i=vnxt[i]) root[x]=modify(root[x],1,R,vver[i]);
    for(int i=head[x];i;i=nxt[i]) dfs(ver[i]),root[x]=merge(root[x],root[ver[i]],1,R);
    for(int i=ghead[x];i;i=gnxt[i]) Ans[gver[i]]=ask(root[x],1,R,1,q2[gver[i]]);
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%s",s),insert(-i);
    scanf("%d",&q);
    int x,y;
    for(int i=1;i<=q;++i){
        scanf("%d",&x);
        if(x==1) scanf("%s",s),++R,insert(R);
        else scanf("%d",&y),q2[i-R]=R,addg(ed[y],i-R);
    }
    build();
    for(int i=1;i<=tot;++i) add(fail[i],i);
    dfs(0);
    for(int i=1;i<=q-R;++i) printf("%d\n",Ans[i]);
    return 0;
}

写的比较丑陋（卡空间卡的心态崩了），见谅~