[NOI2011]阿狸的打字机

听从wzx神仙的指导做了这道题，被洗礼了。

现在感觉我的AC自动机得到了升华。

传送门

其实也没有那么夸张啦。AC自动机fail的指针的性质我很早就知道，只不过对fail树的操作没见过。而且这题的技巧真的很棒。

首先模拟题目描述建出AC自动机，B就是回到父亲，P就是代表一个串结束。

考虑如果没有时间限制，怎么判断x在y中的出现次数，大家一定做过洛谷AC自动机的加强版模板。

回忆一下，那题除了暴力跳fail之外，还有一个做法：

每个点有且只有一个fail指针，而根不算fail指针，将fail指向的点看成自己的爸爸，这样就形成了一棵fail树。

我们暴力统计的时候，每到达一个点是一个单词的末尾，就给这个单词出现次数+1，同时给这个点到根的所有是单词末尾的点都+1。

这样我们只要打好标记，结束后求一遍每个点的子树和，就可以知道他被打了多少次标记了。

选自多弗桃的题解。

这样我们就有了一个暴力，把y相同的询问一起处理，做一遍dfs，设第一行的长度是n，这是一个O(nm/?)的做法，？是询问中y去重后的个数。

考虑优化，单点修改求子树和可以用树状数组维护dfs序解决，但是你每个y都要打一遍标记还是o(n)的。

不慌，每个y串都是有联系的，他们经过前一个串被插入或删除得到，而插入删除的次数是o(n)的。

相当于我们可以在o(n)的时间内遍历所有串，且他们是按1~n的顺序出现的，当一个串出现的时候，我们可以把关于他所有的询问在logn的时间内解决，因此我们要对每个插入删除操作维护当前串的标记，查询时对每个x的末端求子树和。

选自多弗桃的题解。

这题给人启发的是fail树和正常树是一样的，意味着只要你明白在fail树上各个操作的意义，你就可以搞出fail树剖分、fail树dp之类的题来。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct qusch{
    int x,y,h;
}a[100001];
struct node{
    int next,to;
}w[100001];
struct trie{
    int ch[26],fa,fail;
}t[100001];
int ans[100001],n,m,now,num,size[100001],idx[100001];
int head[100001],cnt,heap,tail,team[100001],c[100001];
int pos[100001];
char ch[100001];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int y){while (x<=now){c[x]+=y;x+=lowbit(x);}}
inline int query(int x){int y=0;while (x){y+=c[x];x-=lowbit(x);}return y;}
inline bool cmp(qusch c,qusch d){return c.y<d.y;}
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
void insert(){
    int l=strlen(ch),u=0;
    for (int i=0; i<l; i++){
        if (ch[i]=='B'){u=t[u].fa;continue;}
        if (ch[i]=='P'){pos[++n]=u; continue;}
        int b=ch[i]-'a';
        if (!t[u].ch[b]) t[u].ch[b]=++num;
        t[t[u].ch[b]].fa=u; u=t[u].ch[b];
    }
}
void build(){
    heap=tail=1;
    while (heap<=tail){
        int x=team[heap];
        for (int i=0; i<26; i++){
            if (t[x].ch[i]){
                team[++tail]=t[x].ch[i];
                if (!x) continue;
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
            }
            else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        heap++;
    }
}
void dfs(int x){
    idx[x]=++now; size[x]=1;
    for (int i=head[x]; i; i=w[i].next){
        dfs(w[i].to);
        size[x]+=size[w[i].to];
    }
}
int main(){
    scanf("%s",ch);
    insert(); build();
    for (int i=1; i<=num; i++)
        if (t[i].fail!=i) add(t[i].fail,i);
    scanf("%d",&m);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].h=i;
    }
    sort(a+1,a+m+1,cmp);
    dfs(0); int l=strlen(ch),u=0,k=1,e=0;
    for (int i=0; i<l; i++){
        if (ch[i]=='B'){
            update(idx[u],-1); u=t[u].fa;
            continue;
        }
        if (ch[i]=='P'){
            e++;
            for (int j=k; a[j].y==e; j++){
                int p=pos[a[j].x];
                ans[a[j].h]=query(idx[p]+size[p]-1)-query(idx[p]-1);
                k++;
            }
            continue;
        }
        int b=ch[i]-'a';
        u=t[u].ch[b]; update(idx[u],1);
    }
    for (int i=1; i<=m; i++) printf("%d\n",ans[i]);
    return 0;
}