bzoj 2434: [Noi2011]阿狸的打字机

.

题意：自己看
题解：AC自动机+树状数组
按照题意建出AC自动机。问x在y中出现多少次，就是y的有几个位置跳若干次fail可以到x。所以我们就可以建fail树，从fail到i建边，将y的点+1，统计x的子树的和。这个可以用dfs序+树状数组实现。
代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;

struct trie
{
    int s[26],fail,fa;
}tr[100010];
int tn=0,m,len,pos[100010],n=0,num=0,fst[100010],nn=0,l[100010],r[100010],sum[100010],ans[100010];
char s[100010];
struct edge
{
    int x,y,n;
}e[100010];
vector<pa>q[100010];

void ins(int x,int y)
{
    e[++num]={x,y,fst[x]};
    fst[x]=num;
}
inline void btrie()
{
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(s[i]=='B')
        now=tr[now].fa;
        else if(s[i]=='P')
        pos[++n]=now;
        else
        {
            if(!tr[now].s[s[i]-'a'])
            {
                tr[now].s[s[i]-'a']=++tn;
                tr[tn].fa=now;
            }
            now=tr[now].s[s[i]-'a'];
        }
    }
}
inline void bfail()
{
    queue<int>q;
    for(int i=0;i<26;i++)
    if(tr[0].s[i])
    q.push(tr[0].s[i]);
    while(!q.empty())
    {
        int x=q.front();
        for(int i=0;i<26;i++)
        {
            if(!tr[x].s[i])
            continue;
            int j=tr[x].fail;
            while(j&&!tr[j].s[i])
            j=tr[j].fail;
            if(tr[j].s[i])
            j=tr[j].s[i];
            tr[tr[x].s[i]].fail=j;
            q.push(tr[x].s[i]);
        }
        q.pop();
    }
}
inline void btree()
{
    for(int i=1;i<=tn;i++)
    ins(tr[i].fail,i);
}
void dfs(int x)
{
    l[x]=++nn;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        dfs(y);
    }
    r[x]=nn;
}
int lb(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    for(int i=x;i<=nn;i+=lb(i))
    sum[i]+=y;
}
int get(int x)
{
    if(x==0)
    return 0;
    int ans=0;
    for(int i=x;i>0;i-=lb(i))
    ans+=sum[i];
    return ans;
}
int main()
{
    scanf("%s%d",s,&m);
    len=strlen(s);
    btrie();
    bfail();
    btree();
    dfs(0);/*
    for(int i=0;i<=tn;i++)
    {
        printf("i:%d fa:%d fail:%d s:",i,tr[i].fa,tr[i].fail);
        for(int j=0;j<26;j++)
        printf("%d ",tr[i].s[j]);
        puts("");
    }
    for(int i=1;i<=num;i++)
    printf(" %d %d\n",e[i].x,e[i].y);
    for(int i=0;i<=tn;i++)
    printf(" %d %d\n",l[i],r[i]);*/
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        q[y].push_back(make_pair(x,i));
    }
    n=0;
    int now=0;
    for(int i=0;i<len;i++)
    {
        if(s[i]=='B')
        {
            add(l[now],-1);
            now=tr[now].fa;
        }
        else if(s[i]=='P')
        {
            n++;
            for(int j=0;j<q[n].size();j++)
            {
                ans[q[n][j].second]=get(r[pos[q[n][j].first]])-get(l[pos[q[n][j].first]]-1);
            }
        }
        else
        {
            now=tr[now].s[s[i]-'a'];
            add(l[now],1);
        }/*
        printf("now:%d\n",now);
        for(int i=1;i<=nn;i++)
        printf("%d ",get(i)-get(i-1));
        puts("");*/
    }
    for(int i=0;i<m;i++)
    printf("%d\n",ans[i]);
}