P5840-[COCI2015]Divljak 题解

本文主要是介绍P5840-[COCI2015]Divljak 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P5840-[COCI2015]Divljak

200行代码。。

题意：给一些模式串和q次操作，每次可以把一个新匹配串扔进一个集合里，或者询问当前集合里所有匹配串有几个包含某模式串。

题解：首先是多模匹配，把模式串全扔到ac自动机上，建fail树。

对于操作一：匹配串扔进去后会对经过的所有节点与父节点的链上有贡献。而且就算多次跑到同一个点，由于是同一个匹配串，最多贡献只能计算为1，那么转化为在fail树上的一些点，往他们与根结点的链交集上加一。询问的时候只询问一个节点的值，链交上所有点都更新的话代价太大，考虑转化成树上差分+求带修的子树和，做法是：跑出fail树的dfs序，在链交集上把所有节点按dfs序排序，然后把所有节点权值+1，相邻节点的lca处权值-1，这样的树上差分操作才能保证正确（！）。

对于操作二：只需按dfs序建立线段树，维护权值，允许单点加减和区间查询（dfs序号到dfs+siz即为子树和）。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e6+10;
int n,cnt=1,tot;
struct aczdj{
    int vis[30],fail,ans1;
    int end;
}ac[maxn];
int mp[maxn],rd[maxn],dfn[maxn],rdfn[maxn],siz[maxn];
vector<int> yuan[maxn];
void build1(string now,int biao){
    int now1=now.length(),now2=1;
    for(int i=0;i<now1;i++){
        int v=now[i]-'a'+1;
        if(!ac[now2].vis[v]){
            ac[now2].vis[v]=++cnt;
        }
        now2=ac[now2].vis[v];
    }
    ac[now2].end=biao;
    mp[biao]=now2;
}
void buildfail(){
    queue<int> k1;
    for(int i=1;i<=26;i++) ac[0].vis[i]=1;
    k1.push(1);
    while(!k1.empty()){
        int tmp=k1.front();k1.pop();
        int fl=ac[tmp].fail;
        for(int i=1;i<=26;i++){
            int v=ac[tmp].vis[i];
            if(!v) ac[tmp].vis[i]=ac[fl].vis[i];
            else{
                ac[v].fail=ac[fl].vis[i];
                yuan[ac[fl].vis[i]].push_back(v);
                rd[v]++;
                k1.push(v);
            }
        }
    }
}
int dep[maxn],fat[maxn][60],lg[maxn];
void dfs(int now,int fa){
    dfn[now]=++tot;rdfn[tot]=now;
    siz[now]=1;
    dep[now]=dep[fa]+1;
    fat[now][0]=fa;
    for(int i=1;i<=lg[dep[now]];i++) fat[now][i]=fat[fat[now][i-1]][i-1];
    for(int i=0;i<yuan[now].size();i++){
        int v=yuan[now][i];
        if(v==fa) continue;
        dfs(v,now);
        siz[now]+=siz[v];
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    while(dep[v]>dep[u]) v=fat[v][lg[dep[v]-dep[u]]-1];
    if(u==v) return u;
    for(int i=lg[dep[v]];i>=0;i--){
        if(fat[u][i]!=fat[v][i]){
            u=fat[u][i];
            v=fat[v][i];
        }
    }
    return fat[v][0];
}
struct node{
    int zhi;
}all[maxn*4];
void pushup(int now){all[now].zhi=all[now*2].zhi+all[now*2+1].zhi;}
void build(int now,int lo,int ro){
    if(lo==ro) return;
    build(now*2,lo,mid);
    build(now*2+1,mid+1,ro);
}
void upd(int now,int lo,int ro,int pos,int zhi){
    if(lo==ro&&lo==pos){
        all[now].zhi+=zhi;
        return;
    }
    if(pos<=mid) upd(now*2,lo,mid,pos,zhi);
    else upd(now*2+1,mid+1,ro,pos,zhi);
    pushup(now);
}
void acque(string &now){
    vector<int> k2;
    int now1=now.length(),now2=1;
    for(int i=0;i<now1;i++){
        int v=now[i]-'a'+1;
        now2=ac[now2].vis[v];
        k2.push_back(dfn[now2]);
    }
    sort(k2.begin(),k2.end());
    for(int i=0;i<k2.size();i++){
        if(i&&k2[i]==k2[i-1]) continue;
        upd(1,1,tot,k2[i],1);
        if(i){
            int fat1=lca(rdfn[k2[i]],rdfn[k2[i-1]]);
            upd(1,1,tot,dfn[fat1],-1);
        }
    }
}
ll req(int now,int lo,int ro,int lo1,int ro1){
    if(lo>=lo1&&ro<=ro1){
        return all[now].zhi;
    }
    if(lo>ro1||ro<lo1) return 0;
    ll ans1=0;
    if(mid>=lo1) ans1+=req(now*2,lo,mid,lo1,ro1);
    if(mid<ro1) ans1+=req(now*2+1,mid+1,ro,lo1,ro1);
    return ans1;
}
signed main(){
    for(int i=1;i<=2e6;i++){
        lg[i]=lg[i-1];
        if(i==(1<<lg[i])) lg[i]++;
    }
    cin>>n;string yuan1;
    for(int i=1;i<=n;i++){
        cin>>yuan1;
        build1(yuan1,i);
    }
    buildfail();
    dfs(1,0);
    build(1,1,tot);
    int q;cin>>q;
    while(q--){
        int a1,a2;cin>>a1;
        if(a1==1){
            string p1;cin>>p1;
            acque(p1);
        }
        else{
            cin>>a2;
            cout<<req(1,1,tot,dfn[mp[a2]],dfn[mp[a2]]+siz[mp[a2]]-1)<<endl;
        }
    }
    return 0;
}

这篇关于P5840-[COCI2015]Divljak 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！