CF163E e-Government 题解

· · 题解

CF163E e-Government 题解

题面大意

传送门。

解题思路

比较毒瘤的数据结构拼字符串。

忽略添加和删除操作的话，这就是一个裸的 AC 自动机。

不会 AC 自动机的可以先看这道模板题。

注意到只要求所有模式串匹配的答案，所以从贡献的角度推导。

考虑从 AC 自动机的本质操作分析：

记一个字符串被插入字典树后，在代表它的节点中，最深的那个为关键点。

在匹配的时候，我们通过跳 fail 来查找字典树上能匹配上的点，然后往上跳 fail 计算答案。这个操作相当于从 fail 树上的一个点跳到编号为 0 的根。

在模板题中，这么做会超时。有一种优化思路，是预处理每个节点（包括其本身）跳 fail 能找到的关键点（即模式串完全匹配成功）数量，在某个点匹配成功时，直接加上预处理的值。

是否可以通过维护 fail 树上所有节点跳到根节点路径上的关键点数量呢？

事实上完全可以。

当某个模式串被删去后，只“抹去”关键点，让关键点变为普通点。

因为我们的贡献都在 fail 树上某个节点跳到根节点的路径上，所以“抹去”关键点只会对关键点及其子树的节点的贡献产生影响。只需要批量对子树的每个点贡献减去 1 即可。

增加操作同理。

每次匹配成功，加贡献的时候，现场查询并加入答案。

我们只需要一个数据结构，支持树上的子树修改，单点查询，就能做完这题。

考虑将 fail 树按 dfs 序拍成一个序列，于是转化为区间修改，单点查询。考虑用线段树维护。

如果你想搬树剖板子过来我也不好说什么。

但是，此题的空间限制很毒瘤，线段树可能过不了，所以把原问题转化为差分数组上的单点修改，区间询问前缀和，用树状数组处理。

总的时间复杂度约为 O(n\log n)，可以通过本题。

虽然空间复杂度是 O(n) 的，但是要注意合理分配空间使用！

参考代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e6+10;
int lowbit(int x){
    return x&(-x);
}
struct sb{
    int to,nxt;
}edge[2*N];
int head[N];
int ntt;
void add(int u,int v){
    edge[++ntt]={v,head[u]};
    head[u]=ntt;
}
bool is_end[N];
int dfn[N],conb[N],in[N],out[N];
int tmr;
void dfs(int x,int last,int ttt){
    if(is_end[x]) ttt++;
    dfn[x]=++tmr;
    in[x]=tmr;
    conb[tmr]=ttt;
    for(int i=head[x];i!=-1;i=edge[i].nxt){
        if(edge[i].to==last) continue;
        dfs(edge[i].to,x,ttt);
    }
    out[x]=tmr;
}
struct node{
    int son[26];
}trie[N];
int cnt;
int fail[N];
char str[N];
int ins(int &pos,int sp,int len){
    int fa=0,now=trie[0].son[str[0]-'a'];
    while(true){
        sp++;
        if(!now) now=++cnt;
        trie[fa].son[str[sp]-'a']=now;
        if(sp==len-1) return now;
        fa=now;
        now=trie[now].son[str[sp+1]-'a'];
    }
}
queue<int> q;
int a[N];
bool exi[N];
int trans[N];
int root;
void upd(int x,int v){
    while(x<=tmr){
        a[x]+=v;
        x+=lowbit(x);
    }
}
int ask(int x){
    int tmp=0;
    while(x>0){
        tmp+=a[x];
        x-=lowbit(x);
    }
    return tmp;
}
void build_fail(){
    while(!q.empty()) q.pop();
    for(int i=0;i<26;i++){
        if(trie[0].son[i]) q.push(trie[0].son[i]);
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(!trie[now].son[i]) continue;
            int j=fail[now];
            while(j!=0&&!trie[j].son[i]){
                j=fail[j];
            }
            fail[trie[now].son[i]]=trie[j].son[i];
            q.push(trie[now].son[i]);
        }
    }
    for(int i=1;i<=cnt;i++){
        add(i,fail[i]);
        add(fail[i],i);
    }
    dfs(0,-1,0);
    for(int i=1;i<=tmr;i++){
        upd(i,conb[i]-conb[i-1]);
    }
}
int vst[N]; 
char s[N];
int n,k,ml;
int comp(){
    int tt=0,zyhlqr=0;
    for(int i=0;i<ml;i++){
        while(tt&&!trie[tt].son[s[i]-'a']) tt=fail[tt];
        tt=trie[tt].son[s[i]-'a'];
        zyhlqr+=ask(in[tt]);        
    }
    return zyhlqr;
}
char xh[N];
int main(){
    memset(head,-1,sizeof(head));
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>str;
        trans[i]=ins(root,-1,strlen(str));
        is_end[trans[i]]=true;
        exi[i]=true;
    }
    build_fail();
    while(n--){
        cin>>xh;
        int tlen=strlen(xh);
        if(xh[0]=='?'){
            ml=0;
            for(int i=1;i<tlen;i++){
                s[ml++]=xh[i];
            }
            cout<<comp()<<'\n';
        }else if(xh[0]=='+'){
            int num=0;
            for(int i=1;i<tlen;i++){
                num*=10;
                num+=xh[i]-'0';
            }
            if(exi[num]) continue;
            exi[num]=true;
            upd(in[trans[num]],1);
            upd(out[trans[num]]+1,-1);
        }else{
            int num=0;
            for(int i=1;i<tlen;i++){
                num*=10;
                num+=xh[i]-'0';
            }
            if(!exi[num]) continue;
            exi[num]=false;
            upd(in[trans[num]],-1);
            upd(out[trans[num]]+1,1);
        }
    }
    return 0;
}

本代码可以通过 CF 的评测。

Written by toolong114514 on 2024/6/13.