【BZOJ 2434】 [Noi2011]阿狸的打字机 fail树+树状数组

就是考了一个fail树的神奇应用我们建出fail树之后，发现我们就是在求y到根的路径上所有的点在以x为根的子树里的个数，这个我们离线后用树状数组+dfs序即可解决

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

const int N=;

char s[N];

struct Trie{

  int ch[],fail,fa,deep;

}node[N];

std::vector<int> mem[N];

int sz;

struct V{

  int to,next;

}c[N];

struct VQ{

  int to,next,id;

}ques[N];

int head[N],t,num,ques_head[N],ques_t;

int belong[N],q[N],l[N],r[N],Time;

int T[N],ans[N],m,n;

inline int Q(int pos){

  int ret=;

  for(;pos>;pos-=pos&(-pos))

    ret+=T[pos];

  return ret;

}

inline void U(int pos,int key){

  for(;pos<=n;pos+=pos&(-pos))

    T[pos]+=key;

}

inline void add(int x,int y){

  c[++t].to=y,c[t].next=head[x],head[x]=t;

}

inline void ques_add(int x,int y,int z){

  ques[++ques_t].to=y,ques[ques_t].next=ques_head[x],ques_head[x]=ques_t,ques[ques_t].id=z;

}

void dfs(int x){

  l[x]=++Time;

  for(int i=head[x];i;i=c[i].next)

    dfs(c[i].to);

  r[x]=Time;

}

void dfs_(int x){

  U(l[x],);

  for(int i=;i<mem[x].size();i++)

    for(int j=ques_head[mem[x][i]];j;j=ques[j].next)

      ans[ques[j].id]=Q(r[belong[ques[j].to]])-Q(l[belong[ques[j].to]]-);

  for(int i=;i<;i++)

    if(node[node[x].ch[i]].deep>node[x].deep)

      dfs_(node[x].ch[i]);

  U(l[x],-);

}

int main(){

  scanf("%s",s);

  int now=;

  for(int i=;s[i];i++){

    if(s[i]=='P'){

      belong[++num]=now;

      mem[now].push_back(num);

      continue;

    }

    if(s[i]=='B'){

      now=node[now].fa;

      continue;

    }

    if(!node[now].ch[s[i]-'a'])node[now].ch[s[i]-'a']=++sz,node[sz].fa=now,node[sz].deep=node[now].deep+;

    now=node[now].ch[s[i]-'a'];

  }

  n=sz+;

  q[]=;

  for(int i=,j=;i<=j;i++)

    for(int l=;l<;l++)

      if(node[q[i]].ch[l]){

        q[++j]=node[q[i]].ch[l];

        node[q[j]].fail=q[i]?node[node[q[i]].fail].ch[l]:;

        add(node[q[j]].fail,q[j]);

      }else

        node[q[i]].ch[l]=q[i]?node[node[q[i]].fail].ch[l]:;

  dfs();

  scanf("%d",&m);

  for(int i=,x,y;i<=m;i++)

    scanf("%d%d",&x,&y),ques_add(y,x,i);

  dfs_();

  for(int i=;i<=m;i++)

    printf("%d\n",ans[i]);

  return ;

}