题解 P4947 【PION后缀自动机】

mrsrz · 2019-06-05 13:00:55 · 题解

一道比较简单的数据结构题。

如果只有一种字符串，那么我们可以直接树链剖分+线段树来解决。

这里有多种字符串，那么我们还是树链剖分，然后对每种不同的字符串开线段树就可以了。空间用动态开点来解决。

操作2、3就是基本的线段树区间修改区间查询。操作1直接询问LCA即可。

对于判断字符串相等的问题，由于字符串长度不超过6，因此我们把字符串看做一个27进制数，用long long存，map离散化即可。

设字符串总数为S，则时间复杂度O(n+m\log^2 n+S\log n)，空间复杂度O(n+S\log n)。

Code：

#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
const int N=1e5+5,M=N*5;
char ss[233];
vector<int>G[N];
int n,m,fa[N],son[N],top[N],sz[N],dfn[N],idx,dep[N],rt[M],ls[M*20],rs[M*20],d[M*20],tot,num;
map<LL,int>ys;
inline LL Hx(char*s,int n){
    LL ret=0,x=1;
    for(int i=2;i<n;++i,x*=27)
    ret+=(s[i]-'a'+1)*x;
    return ret;
}
void dfs(int now){
    sz[now]=1;
    for(int to:G[now])
    if(!dep[to]){
        dep[to]=dep[now]+1,fa[to]=now,dfs(to);
        sz[now]+=sz[to];
        if(!son[now]||sz[son[now]]<sz[to])son[now]=to;
    }
}
void dfs2(int now){
    dfn[now]=++idx;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int to:G[now])
    if(to!=son[now]&&to!=fa[now])dfs2(top[to]=to);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
inline int dist(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}
void add(int&o,int l,int r,const int&pos){
    if(!o)o=++tot;
    ++d[o];
    if(l<r){
        const int mid=l+r>>1;
        if(pos<=mid)add(ls[o],l,mid,pos);else add(rs[o],mid+1,r,pos);
    }
}
int erase(int&o,int l,int r,const int&L,const int&R){
    if(!o)return 0;
    int ret=0;
    if(L<=l&&r<=R){
        ret+=d[o],o=0;return ret;
    }
    const int mid=l+r>>1;
    if(L<=mid)ret+=erase(ls[o],l,mid,L,R);
    if(mid<R)ret+=erase(rs[o],mid+1,r,L,R);
    d[o]=d[ls[o]]+d[rs[o]];
    if(!d[o])o=0;
    return ret;
}
int erase(int&o,int x,int y){
    int ret=0;
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])
    ret+=erase(o,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];else
    ret+=erase(o,1,n,dfn[top[y]],dfn[y]),y=fa[top[y]];
    if(dep[x]<dep[y])ret+=erase(o,1,n,dfn[x],dfn[y]);else ret+=erase(o,1,n,dfn[y],dfn[x]);
    return ret;
}
int query(int o,int l,int r,const int&L,const int&R){
    if(!o)return 0;
    if(L<=l&&r<=R)return d[o];
    const int mid=l+r>>1;
    if(L<=mid&&mid<R)return query(ls[o],l,mid,L,R)+query(rs[o],mid+1,r,L,R);
    if(L<=mid)return query(ls[o],l,mid,L,R);return query(rs[o],mid+1,r,L,R);
}
int query(int o,int x,int y){
    int ret=0;
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])
    ret+=query(o,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];else
    ret+=query(o,1,n,dfn[top[y]],dfn[y]),y=fa[top[y]];
    if(dep[x]<dep[y])ret+=query(o,1,n,dfn[x],dfn[y]);else ret+=query(o,1,n,dfn[y],dfn[x]);
    return ret;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs(dep[1]=1),dfs2(1);
    ss[0]=ss[1]=' ';
    for(int i=1,k;i<=n;++i)
    for(cin>>k;k--;){
        cin>>(ss+2);
        LL hx=Hx(ss,strlen(ss));
        if(!ys.count(hx))ys[hx]=++num;
        add(rt[ys[hx]],1,n,dfn[i]);
    }
    while(m--){
        cin>>ss;
        if(*ss=='q'){
            cin>>ss;
            if(ss[1]=='p'){
                int u,v;
                cin>>u>>v;
                cout<<dist(u,v)<<'\n';
            }else{
                int u,v;
                cin>>u>>v>>ss;
                LL hx=Hx(ss,strlen(ss));
                if(!ys.count(hx))cout<<"0\n";else
                cout<<query(rt[ys[hx]],u,v)<<'\n';
            }
        }else{
            int u,v;
            cin>>ss>>u>>v>>ss;
            LL hx=Hx(ss,strlen(ss));
            if(!ys.count(hx))cout<<"0\n";else
            cout<<erase(rt[ys[hx]],u,v)<<'\n';
        }
    }
    return 0;
}