bzoj 2434 [Noi2011]阿狸的打字机（fail树+离线处理+BIT）

【题目链接】

　　http://www.lydsy.com/JudgeOnline/problem.php?id=2434

【题意】

　　按照一定规则生成n个字符串，回答若干个询问：(x,y)，问第x个字符串在第y个字符串中的出现次数。

【思路】

用所有的串构建AC自动机并求出fail数组，利用fail指针构建fail树，在这棵树上父亲是儿子的最大后缀。对于询问（x，y），设自动机中y对应的尾节点为pos，即统计自动机上pos-root的路径上的结点中有多少个处于fail树中的x的子树中。

一棵树的子树中的所有节点对应于dfs序上的一段连续区间，求出dfs序后，统计就可以转化为区间和问题，用到BIT。

离线处理所有的询问，统计所有关于y的询问到que[y]，再用O(n)加一遍节点，我们对路上的所有节点对应+1，当访问到节点rt时，root-rt路径上的所有节点都已经访问，处理关于rt的询问即可。

总的时间复杂度为O(nlogn)。

【代码】

  1 #include<cstdio>
  2 #include<vector>
  3 #include<queue>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
  8 using namespace std;
  9 
 10 const int N = 1e5+10;
 11 char s[N];
 12 int C[N],ans[N],n;
 13 vector<pair<int,int> > que[N];
 14 
 15 void add(int x,int v) {
 16     while(x<N) C[x]+=v,x+=x&-x;
 17 }
 18 int query(int x) {
 19     int res=0;
 20     while(x) res+=C[x],x-=x&-x;
 21     return res;
 22 }
 23 struct ACauto {
 24     int sz,ch[N][26],fa[N],l[N],r[N],pos[N],f[N],dfsc;
 25     vector<int> g[N];
 26     ACauto() { sz=1;dfsc=0; memset(ch,0,sizeof(ch)); }
 27     void insert() {
 28         int u=0,id=0;
 29         for(int i=0;s[i];i++) {
 30             if(s[i]=='P') pos[++id]=u;
 31             else if(s[i]=='B') u=fa[u];
 32             else {
 33                 int c=s[i]-'a';
 34                 if(!ch[u][c]) {
 35                     ch[u][c]=sz; fa[sz]=u; sz++;
 36                 }
 37                 u=ch[u][c];
 38             }
 39         }
 40     }
 41     void get_Fail() {
 42         queue<int> q;
 43         f[0]=0;
 44         for(int c=0,v;c<26;c++)
 45             if(ch[0][c]) f[ch[0][c]]=0,q.push(ch[0][c]);
 46         while(!q.empty()) {
 47             int qr=q.front(); q.pop();
 48             for(int c=0;c<26;c++) {
 49                 int u=ch[qr][c];
 50                 if(!u) continue;
 51                 q.push(u); int v=f[qr];
 52                 while(v&&!ch[v][c]) v=f[v];
 53                 f[u]=ch[v][c];
 54             }
 55         }
 56         for(int i=1;i<sz;i++)
 57             g[f[i]].push_back(i);
 58     }
 59     void get_dfsc(int u) {
 60         l[u]=++dfsc;
 61         for(int i=0;i<g[u].size();i++)
 62             get_dfsc(g[u][i]);
 63         r[u]=dfsc;
 64     }
 65     void solve() {
 66         int id=0,u=0;
 67         add(l[0],1);
 68         for(int i=0;s[i];i++) {
 69             if(s[i]=='P') {
 70                 id++;
 71                 for(int j=0;j<que[id].size();j++) {
 72                     int x=pos[que[id][j].first];
 73                     ans[que[id][j].second]=query(r[x])-query(l[x]-1);
 74                 }
 75             }
 76             else if(s[i]=='B') add(l[u],-1),u=fa[u];
 77             else u=ch[u][s[i]-'a'],add(l[u],1);
 78         }
 79     }
 80 }ac;
 81 
 82 void read(int& x) {
 83     char c=getchar(); int f=1; x=0;
 84     while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
 85     while(isdigit(c)) x=x*10+c-'0',c=getchar();
 86     x*=f;
 87 }
 88 int main() {
 89     scanf("%s",s);
 90     ac.insert();
 91     ac.get_Fail();
 92     ac.get_dfsc(0);
 93     read(n);
 94     int x,y;
 95     for(int i=0;i<n;i++) {
 96         read(x),read(y);
 97         que[y].push_back(make_pair(x,i));
 98     }
 99     ac.solve();
100     for(int i=0;i<n;i++)
101         printf("%d
",ans[i]);
102     return 0;
103 }