Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
Sample Output
HINT
1<=N<=10^5
Source
【题解】
isprogrammer炸掉了一个星期真是不爽
做这道题让窝感觉没学过trie图。。。。。
首先要用黑暗的方法构出trie树，即按照读入顺序扫下来，那么有三种情况：
1、碰到字母，新建一个子节点（如果已存在就不用新建），进入该子节点。
2、碰到P，那么打个标记。
3、碰到B，回到父亲节点。
然后求出每个节点的fail，那么询问x在y中出现多少次，只要求root~y中有多少点沿fail能走到x。
那么构出fail树，问题就转化为x的子树中有多少个是root~y中的点。
考虑dfs序，那么求子树和的问题就转化为求片段和，可以用树状数组维护。
对于一个串y，将root~y的点的dfs序插入树状数组中，然后处理所有与y有关的询问就阔以辣！
最后的处理还是可以直接扫描读入的串：
1、碰到字母，将子节点的dfs序加入树状数组，进入该子节点。
2、碰到P，处理询问。
3、碰到B，回到父亲节点。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int m,cnt,u,id,i,x,y,edgenum,Edgenum,T;
char s[M];
int pos[M],fa[M],head[M],vet[M],next[M],Head[M],Vet[M],Next[M],tree[2*M],fail[M],h[M],l[M],r[M],ans[M];
int trie[M][26];
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
void Addedge(int x,int y){
Vet[++Edgenum]=y;
Next[Edgenum]=Head[x];
Head[x]=Edgenum;
}
void update(int x,int y){
for (int i=x;i<=T;i+=i&-i)tree[i]+=y;
}
int query(int x){
int ans=0;
for (int i=x;i;i-=i&-i)ans+=tree[i];
return ans;
}
void bfs(){
int l=1,r=1;
h[l]=1,fail[1]=0;
while (l<=r){
int u=h[l];
for (int i=0;i<26;i++)
if (trie[u][i]){
int v=trie[u][i];
if (u==1)fail[v]=1;else fail[v]=trie[fail[u]][i];
h[++r]=v;
}else trie[u][i]=trie[fail[u]][i];
l++;
}
}
void dfs(int u){
l[u]=++T;
for (int e=head[u];e;e=next[e])dfs(vet[e]);
r[u]=++T;
}
int main(){
scanf("%s",s);
scanf("%d",&m);
int n=strlen(s);
cnt=1,u=1,id=0;
for (i=0;i<26;i++)trie[0][i]=1;
for (i=0;i<n;i++){
if (s[i]-'a'>=0){
if (!trie[u][s[i]-'a'])trie[u][s[i]-'a']=++cnt,fa[cnt]=u;
u=trie[u][s[i]-'a'];
}else if (s[i]=='P')pos[++id]=u;else u=fa[u];
}
bfs();
for (i=1;i<=cnt;i++)addedge(fail[i],i);
dfs(0);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
Addedge(y,x);
}
u=1,id=0;update(l[1],1);
for (i=0;i<n;i++){
if (s[i]-'a'>=0)u=trie[u][s[i]-'a'],update(l[u],1);
else if (s[i]=='P'){
id++;
for (int e=Head[id];e;e=Next[e]){
int v=pos[Vet[e]];
ans[e]=query(r[v])-query(l[v]-1);
}
}else update(l[u],-1),u=fa[u];
}
for (i=1;i<=m;i++)printf("%d\n",ans[i]);
}
评论 (0)
