【解题报告】[NOI2011]阿狸的打字机

题目链接

---

前言

Captain Orange 讲课作业其76，大概思路属于一眼题，但各种各样的毒瘤优化才是本题的关键

题解

看到题目第一眼，相信已经有了大概的思路

建AC自动机，对于每个询问暴力查找 $y$ 串中有多少个位置的 $fail$ 指针指向 $x$ 串的终止节点
如果按照这个思路打，可以得到 $30pts$

想办法进行优化，发现在询问中，可能会出现一个串作为多个 $y$ 串出现，很容易想到，我们可以用一个将询问离线处理到一个桶中，这样对一个 $y$ 串的处理过程就能够处理多组询问
这样就可以得到 $70pts$

观察性质，我们发现每个结点对其 $fail$ 指针指向的结点贡献为 $1$ ,转化一下思路，我们将 $fail$ 指针反过来连线，发现对于每个 $x$ 其答案为终止点的子树大小和，我们只需要统计子树大小和即可
可惜的是，这样仍然只有 $70pts$

考虑再进行优化，我们对于每一条串按照 $fail$ 指针倒着连边后并记录当前结点编号，以及从当前结点出发最远可以到达的结点，这样我们就转化成了一个序列问题，每次求一段区间的和。
很显然的，我们可以用树状数组优化区间和: 从原tire树上遍历，遍历到当前结点即将当前结点的编号处的值修改为 $1$ ，遍历结束后再修改为 $0$ 。当遍历到当前串的终止节点时，我们对其作为 $y$ 串的每个询问统计答案即可
这样能够得到 $100pts$

后记

除了以上部分，还有一些需要注意的地方。

在插入 $tire$ 时，我们不需要每个 $P$ 字符都插入当前串，我们只需要在在遍历输入字符串时，顺便维护一个 $now$ ，并在每个 $P$ 字符标记终止，同时记录一个 $fa$ ，在每个 $B$ 字符处将 $now$ 回退到 $fa[now]$

在统计答案的遍历时，我们遍历的是原tire树，而我们求 $fail$ 指针的过程中会破坏tire树的结构，因此我们需要将原tire树备份

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=500005;
const int inf=0x3f3f3f3f;
int m,tot,id,cnt_edge,head[maxn],ed[maxn];
int bfn[maxn],low[maxn],cnt,ott,ans[maxn];
int su[maxn],taxr[maxn],taxl[maxn];
char s[maxn];
struct node
{
    int ch[26],fail,fa,id;
    int nch[26];
}tr[maxn];
struct edge
{
    int v,last;
}e[maxn<<2];
struct ques
{
    int x,y,id;
    friend bool operator <(ques a,ques b){return a.y<b.y;}
}qe[maxn];

inline int read(void)
{
    int num,sign=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')sign=0;
    num=c-'0';
    while(isdigit(c=getchar()))num=(num<<3)+(num<<1)+c-'0';
    return sign?num:-num;
}

inline void get_fail(void)
{
    queue<int>q;
    for(register int i=0;i<26;++i)
        if(tr[0].ch[i])q.push(tr[0].ch[i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(register int i=0;i<26;++i)
        {
            if(tr[u].ch[i])
            {
                tr[tr[u].ch[i]].fail=tr[tr[u].fail].ch[i];
                q.push(tr[u].ch[i]);
            }
            else
                tr[u].ch[i]=tr[tr[u].fail].ch[i];
        }
    }
}

inline void addedge(int u,int v){e[++cnt_edge].last=head[u],e[cnt_edge].v=v,head[u]=cnt_edge;}
void dfs(int u)
{
    bfn[u]=++cnt;
    for(register int i=head[u];i;i=e[i].last)dfs(e[i].v);
    low[u]=cnt;
}
inline void modify(int x,int d){for(;x<=cnt;x+=x&-x)su[x]+=d;}
inline int sum(int x){int res=0;for(;x;x-=x&-x)res+=su[x];return res;}
void dfs2(int u)
{
    modify(bfn[u],1);
    if(tr[u].id)
        for(register int i=taxl[tr[u].id];i<=taxr[tr[u].id];++i)
            ans[qe[i].id]=sum(low[ed[qe[i].x]])-sum(bfn[ed[qe[i].x]]-1);
    for(register int i=0;i<26;++i)
        if(tr[u].nch[i])dfs2(tr[u].nch[i]);
    modify(bfn[u],-1);
}


signed main(void)
{
    freopen("P2414_2.in","r",stdin);
    scanf("%s",s+1);
    int len=strlen(s+1);
    int st=1;
    while(s[st]=='P'||s[st]=='B')++st;
    for(register int u=0,i=st;i<=len;++i)
    {
        if(s[i]=='P')
            tr[u].id=++id,ed[id]=u;
        else if(s[i]=='B')
            u=tr[u].fa;
        else
        {
            if(!tr[u].ch[s[i]-'a'])tr[u].ch[s[i]-'a']=++tot,tr[tot].fa=u;
            u=tr[u].ch[s[i]-'a'];
        }
    }
    for(register int i=0;i<=tot;++i)
        for(register int j=0;j<26;++j)
            tr[i].nch[j]=tr[i].ch[j];
    get_fail();
    for(register int i=1;i<=tot;++i)addedge(tr[i].fail,i);
    dfs(0);
    m=read();
    for(register int i=1;i<=m;++i)qe[i].x=read(),qe[i].y=read(),qe[i].id=i;
    sort(qe+1,qe+1+m);
    for(register int i=1,pos=1;i<=m;i=pos)
    {
        taxl[qe[i].y]=i;
        while(qe[i].y==qe[pos].y)++pos;
        taxr[qe[i].y]=pos-1;
    }
    dfs2(0);
    for(register int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}