[NOI2011] 阿狸的打字机
题目描述
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 \(28\) 个按键，分别印有 \(26\) 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的：
- 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
- 按一下印有
B的按键，打字机凹槽中最后一个字母会消失。 - 按一下印有
P的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入 aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从 \(1\) 开始顺序编号，一直到 \(n\)。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 \((x,y)\)（其中 \(1\leq x,y\leq n\)），打字机会显示第 \(x\) 个打印的字符串在第 \(y\) 个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
\(n,m\le 10^5\)，第一行的长度不超过 \(10^5\)
考虑建出 AC 自动机，现在要询问在 trie 树上 \(y\) 的所有父亲有多少个是在 \(x\) 的fail 树的子树内。
考虑将 fail 树拍成 dfn，然后在 trie 树上搜索的时候维护所有祖先的信息，然后就是一个单点加减，区间求和，树状数组即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char str[N];
int m,x,y,tg[N],tr[N][26],fa[N],ans[N],fail[N],q[N],l,r,tme,idx,in[N],sz[N],ss[N],ls,to[N],p[N][26];
struct graph{
int hd[N],e_num;
struct edge{
int v,nxt,w;
}e[N<<1];
void add_edge(int u,int v,int w)
{
e[++e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
}
}g,h;
void build()
{
l=1;
for(int i=0;i<26;i++)
if(tr[0][i])
q[++r]=tr[0][i];
while(l<=r)
{
for(int i=0;i<26;i++)
{
if(tr[q[l]][i])
q[++r]=tr[q[l]][i],fail[tr[q[l]][i]]=tr[fail[q[l]]][i];
else
tr[q[l]][i]=tr[fail[q[l]]][i];
}
++l;
}
for(int i=1;i<=idx;i++)
g.add_edge(fail[i],i,0);
}
void insert(char c)
{
if(c=='P')
tg[ls]=1,to[++m]=ls;
else if(c=='B')
ls=fa[ls];
else
{
if(!tr[ls][c-'a'])
tr[ls][c-'a']=++idx,fa[idx]=ls;
ls=tr[ls][c-'a'];
}
}
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void sou(int x)
{
in[x]=++tme,sz[x]=1;
for(int i=g.hd[x];i;i=g.e[i].nxt)
sou(g.e[i].v),sz[x]+=sz[g.e[i].v];
}
int ask(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret+=ss[x];
return ret;
}
void add(int x,int y)
{
for(;x<=tme;x+=x&-x)
ss[x]+=y;
}
void dfs(int x)
{
add(in[x],1);
for(int i=h.hd[x];i;i=h.e[i].nxt)
ans[h.e[i].w]=ask(in[h.e[i].v]+sz[h.e[i].v]-1)-ask(in[h.e[i].v]-1);
for(int i=0;i<26;i++)
if(p[x][i])
dfs(p[x][i]);
add(in[x],-1);
}
int main()
{
scanf("%s",str+1);
for(int i=1;str[i];i++)
insert(str[i]);
memcpy(p,tr,sizeof(p));
build();
m=read();
for(int x,y,i=1;i<=m;i++)
x=read(),y=read(),h.add_edge(to[y],to[x],i);
sou(0);
dfs(0);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}