BZOJ 2434 [Noi2011]阿狸的打字机

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=2434

题意:略。

思路:首先需要观察到这个打字的过程就是在构造一个Trie树,然后考虑询问,可以很容易想到相当于是在fail树上询问字符串x结尾的那个节点为根的子树里有多少个y的节点。但是直接求不好求,所以我们把询问离线,重新走一遍Trie的构建过程,用树状数组维护dfs序的sum值,每走一个节点就单点加一,这样走到一个字符串结尾的时候我们就把这个字符串所有节点都在fail树上权值加一了然后就处理这个字符串的所有询问好了,一堆区间查询sum值,然后就做完了~

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
const int N=1e5+10;
const int SIGMA_SIZE=26;
int T,i,j,tot,dfs_clock,n,m,x,y,cnt,ans[N],sum[N],q[N],fail[N],fa[N],pos[N],L[N],R[N],son[N][SIGMA_SIZE];
char s[N];
vector<int>G[N];
vector<pair<int,int> >qu[N];
inline int lowbit(int x){return x&(-x);}
int get(int x){
    int res=0;
    for (;x>0;x-=lowbit(x)) res+=sum[x];
    return res;
}
void add(int x,int v){for(;x<=dfs_clock;x+=lowbit(x))sum[x]+=v;}
void build(char* s){
    int p=0,id=0;
    for (i=0;s[i];++i){
        if (s[i]=='P') pos[++id]=p;
        else if (s[i]=='B') p=fa[p];
        else{
            int idx=s[i]-'a';
            if (!son[p][idx]){
                son[p][idx]=++tot;
                fa[tot]=p;
            }
            p=son[p][idx];
        }
    }
}
void getfail(){
    int head=0,tail=0;
    for (i=0;i<SIGMA_SIZE;++i){
        if (son[0][i]) q[tail++]=son[0][i];
    }
    for (;head!=tail;){
        int u=q[head++];
        for (i=0;i<SIGMA_SIZE;++i){
            if (son[u][i]){
                fail[son[u][i]]=son[fail[u]][i];
                q[tail++]=son[u][i];
            }
            else son[u][i]=son[fail[u]][i];
        }
    }
}
void dfs(int u){
    L[u]=++dfs_clock;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        dfs(v);
    }
    R[u]=dfs_clock;
}
void solve(){
    int p=0,id=0;   
    add(L[p],1);
    for (i=0;s[i];++i){
        if (s[i]=='P'){
            id++;
            for (j=0;j<(int)qu[id].size();++j){
                int u=qu[id][j].first,idx=qu[id][j].second;
                ans[idx]=get(R[pos[u]])-get(L[pos[u]]-1);
            }
        }
        else if (s[i]=='B'){
            add(L[p],-1);
            p=fa[p];
        }
        else{
            p=son[p][s[i]-'a'];
            add(L[p],1);
        }
    }
}
int main(){
    scanf("%s",s);
    build(s);
    getfail();
    for (i=1;i<=tot;++i) G[fail[i]].PB(i);
    dfs(0);
    for (scanf("%d",&m),i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        qu[y].PB(MP(x,i));
    }
    solve();
    for (i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注