题目地址：洛谷：【P2414】[NOI2011]阿狸的打字机 – 洛谷、BZOJ：Problem 2434. — [Noi2011]阿狸的打字机

题目描述

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。
打字机上只有28个按键，分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现，这个打字机是这样工作的：

• 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
• 按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。
• 按一下印有’P’的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a aa ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

题意简述

你有一个打字机，打字机支持三种操作

• 向序列尾部加入一个字母
• 把当前序列印在纸上并换行
• 丢弃序列尾部的最后一个字母

纸上会被印上若干行文字，现在你有$m$组询问，每组询问求第$x$行的字符串在第$y$行的字符串中出现了几次。

输入输出格式

输入格式：
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。

输出格式：
输出m行，其中第i行包含一个整数，表示第i个询问的答案。

输入输出样例

输入样例#1：

aPaPBbP
3
1 2
1 3
2 3

输出样例#1：

2
1
0

说明

数据范围:
对于100%的数据，n<=100000,m<=100000,第一行总长度<=100000。

题解

首先我们可以对所有串建一个AC自动机，由于上面的操作的一些特殊性质，其实可以一位一位地边操作边插入到Trie树中。
处理每个询问的时候都在AC自动机上跑匹配不现实，会TLE。我们需要一种优化到$O(\log n)$回答单次询问的方法。我们想到了fail树，问$y$中有几个$x$等价于问fail树中$x$的末结点子树中有几个属于$y$路径上的节点。
我们考虑把fail树建出来，处理DFS序，对DFS序建一个树状数组。我们还是按照读入操作的那个顺序去遍历这个Trie树，每到一个节点对树状数组中这个节点DFS序的位置+1，退出一个节点就-1，这样，当到达每个串的结尾节点时，它的Trie树上的树链节点都被+1了，此时对于这个串作为$y$的询问就可以回答了，直接在树状数组上查$x$的子树和就好。
因此，思路是，离线处理这些询问，把询问按$y$分类，每遍历到一个字符串结尾的时候回答该串作为$y$的询问，这样复杂度就是很靠谱的$O(n \log n)$了。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <queue>

const int MAXN = 100005;

char op[MAXN];
int n, m, ans[MAXN];

typedef std::pair<int, int> PII;
std::vector<PII> vec[MAXN];

int ch[MAXN][26], fa[MAXN], fail[MAXN], end[MAXN], tot, stot;
std::vector<int> gra[MAXN];

inline void insert() {
    int p = 0;
    for(int i = 1; i <= n; i++) {
        if(op[i] == 'P') {
            end[++stot] = p;
        } else if(op[i] == 'B') {
            p = fa[p];
        } else {
            int c = op[i] - 'a';
            if(!ch[p][c]) {
                ch[p][c] = ++tot;
                fa[tot] = p;
            }
            p = ch[p][c];
        }
    }
}

std::queue<int> que;

inline void calfail() {
    for(int i = 0; i < 26; i++) {
        if(ch[0][i]) {
            gra[0].push_back(ch[0][i]);
            que.push(ch[0][i]);
        }
    }
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < 26; i++) {
            if(ch[u][i]) {
                int p = fail[u];
                while(p && !ch[p][i]) p = fail[p];
                fail[ch[u][i]] = ch[p][i];
                gra[ch[p][i]].push_back(ch[u][i]);
                que.push(ch[u][i]);
            }
        }
    }
}

int dfn[MAXN], siz[MAXN], clk;

void dfs(int u) {
    dfn[u] = ++clk; siz[u] = 1;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        dfs(v);
        siz[u] += siz[v];
    }
}

int tr[MAXN];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int v) {
    for(int i = x; i <= clk; i += lowbit(i)) {
        tr[i] += v;
    }
}

inline int query(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += tr[i];
    }
    return res;
}

inline void solve() {
    int p = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(op[i] == 'P') {
            cnt++;
            for(int j = 0; j < vec[cnt].size(); j++) {
                int x = vec[cnt][j].first;
                ans[vec[cnt][j].second] += query(dfn[end[x]] + siz[end[x]] - 1) - query(dfn[end[x]] - 1);
            }
        } else if(op[i] == 'B') {
            add(dfn[p], -1);
            p = fa[p];
        } else {
            int c = op[i] - 'a';
            p = ch[p][c];
            add(dfn[p], 1);
        }
    }
}

int main() {
    scanf("%s%d", op + 1, &m); n = strlen(op + 1);
    for(int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        vec[y].push_back(PII(x, i));
    }
    insert();
    calfail();
    dfs(0);
    solve();
    for(int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}