[NOI2011]阿狸的打字机

题目大意：

一个老式的打字机按照如下的方式工作：用一个栈存储想要打印的内容（小写英文字母），B键将栈顶字母出栈，P键将栈中所有字母打印出来。

给定长度为\(n(n\le10^5)\)的操作序列（包含\(26\)个小写字母和操作B、P）。\(m(m\le10^5)\)次询问，第\(x\)个打印出来的字符串在第\(y\)个打印出来的字符串中出现了几次。

思路：

该打字机的特性使得我们可以很容易地构造出一个AC自动机，插入小写字母同普通的AC自动机，B操作时直接将返回到当前结点在Trie上的父亲即可。

将原问题放到Fail树上，就是\(x\)对应的子树中有多少个结点对应着\(y\)。求出Fail树的DFS序，树状数组维护即可。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}const int N=1e5+1,M=1e5;char s[N];int m,par[N],pos[N],in[N],out[N],cnt,ans[M];std::vector
         
           e[N];inline void add_edge(const int &u,const int &v) { e[u].push_back(v); par[v]=u;}struct Query { int x,y,id; bool operator < (const Query &rhs) const { return y