NOI2011 阿狸的打字机

题目:

  阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有 个按键,分别印有 个小写英文字母和 BP 两个字母。 经阿狸研究发现,这个打字机是这样工作的:

  • 输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。
  • 按一下印有 B 的按键,打字机凹槽中最后一个字母会消失。
  • 按一下印有 P 的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失(保证凹槽中至少有一个字母)。

  例如,阿狸输入 aPaPBbP ,纸上被打印的字符如下:

  a
  aa
  ab

  我们把纸上打印出来的字符串从 开始顺序编号,一直到 。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数 (其中 ),打字机会显示第 个打印的字符串在第 个打印的字符串中出现了多少次。
  阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

思路:

  首先打字机的工作流程可以在 Trie 树上模拟,这样就得到了一棵大小为 的 Trie 树。因为要求支持查询一个 串在 串中出现的次数,可以考虑再构造 AC 自动机得到 Fail 树。
  因为子串是前缀的后缀,如果暴力的查询 串在 串中出现的次数,可以沿着 Trie 树遍历 串,经过的每一个点都沿着 Fail 树往上爬,统计碰到 表示 对应的叶子结点)的次数。
  考虑优化先前的暴力,其实要查询 串在 串中出现的次数,也就是查询从 到根的路径中,有多少个点在 Fail 树上是 的儿子。那么只要离线查询,用 Fail 树的 dfs 序和树状数组维护子树和,在树上一次遍历就能得到答案了。复杂度 。(模拟赛的时候没想到离线,用树链剖分加线段树二维数点强行在线,复杂度 )。

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
const int N=1e5+5;
typedef long long ll;

#define erep(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator[] (int x){return W[x];}
};

Link<N,N,int> Fail,Trie;

namespace ACAuto{
    int fa[N],fail[N],ch[N][26],tot;
    void getFail(){
        std::queue<int> q;
        fail[0]=0;
        rep(i,0,25)
            if(ch[0][i]){
                fail[ch[0][i]]=0;
                Fail.add(0,ch[0][i]);
                q.push(ch[0][i]);
            }
            else ch[0][i]=0;
        while(!q.empty()){
            int o=q.front();q.pop();
            rep(i,0,25)
                if(ch[o][i]){
                    fail[ch[o][i]]=ch[fail[o]][i];
                    Fail.add(ch[fail[o]][i],ch[o][i]);
                    q.push(ch[o][i]);
                }
                else ch[o][i]=ch[fail[o]][i];
        }
    }
    void build(char *s,int node[]){
        int o=0,cnt=0;
        while(*s){
            char c=*s++;
            if(c=='B')o=fa[o];
            else if(c=='P')node[++cnt]=o;
            else {
                if(!ch[o][c-'a']){
                    ch[o][c-'a']=++tot;
                    fa[ch[o][c-'a']]=o;
                    Trie.add(o,ch[o][c-'a']);
                }
                o=ch[o][c-'a'];
            }
        }
        getFail();
    }
}

struct BIT{
    int c[N],a;
    #define low(x) (-(x)&(x))
    void upd(int x,int d){
        for(;x<N;x+=low(x))c[x]+=d;
    }
    int qry(int x){
        for(a=0;x;x-=low(x))a+=c[x];
        return a;
    }
    int qry(int l,int r){
        return qry(r)-qry(l-1);
    }
}sum;

int dfn[N],en[N];
void dfs_f(int o){
    static int id=0;
    dfn[o]=++id;
    erep(k,Fail,o)dfs_f(Fail[k]);
    en[o]=id;
}
struct Ques{
    int x,id;
};
Link<N,N,Ques> Qu;
int out[N];
void dfs_t(int o){
    sum.upd(dfn[o],1);
    erep(k,Qu,o){
        Ques q=Qu[k];
        out[q.id]=sum.qry(dfn[q.x],en[q.x]);
    }
    erep(k,Trie,o)dfs_t(Trie[k]);
    sum.upd(dfn[o],-1);
}

char s[N];
int node[N];
int main(){
    // freopen("data.in","r",stdin);
    scanf("%s",s);
    ACAuto::build(s,node);
    int n;
    scanf("%d",&n);
    rep(i,1,n){
        int x,y;
        scanf("%d%d",&x,&y);
        int u=node[x],v=node[y];
        Qu.add(v,(Ques){u,i});
    }
    dfs_f(0);dfs_t(0);
    rep(i,1,n)printf("%d\n",out[i]);
    return 0;
}