题解

构造前缀树

把阿狸的按键序列按照“栈”语义处理：

• 输入小写字母时新增儿子结点；
• B 回退到父亲；
• P 把当前结点的编号记录下来，表示一次打印的字符串。

如此即可得到一棵字典树，树上的每个结点恰好对应某个打印字符串。记 cor[i] 为第 $i$ 次打印所在的结点。

AC 自动机 + 树状数组统计

为了回答“字符串 $x$ 在字符串 $y$ 中出现次数”，等价于把 $y$ 的整串视作主串，统计主串沿途经过的所有结点中，fail 树子树包含 cor[x] 的次数。步骤如下：

1. 在字典树上建 AC 自动机，得到每个结点的 fail 指针，并把 fail 树做 DFS 编号，得到子树区间 [L[u], R[u]]；
2. 离线读入所有询问 $(x,y)$，将其挂在结点 cor[y] 下；
3. 对字典树做 DFS 遍历（这棵树正是“输入过程中 ever 访问到的所有状态”），维护一颗树状数组：进入结点 u 时在 L[u] 位置加一，离开时减一；
4. 当遍历到某个打印结点 cor[y] 时，依次回答挂在其上的询问。对于询问 $(x,y)$，只需查询 cor[x] 在 fail 树上的 DFS 区间和，即为该模式在当前堆栈状态下出现的次数；
5. 由于 P 操作保证了栈非空，遍历顺序与真实输入一致，故答案正确。

树状数组负责区间计数，AC 自动机提供“包含关系”。复杂度为 $O(\text{输入长度} + m \log n)$。

参考代码

#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

struct BIT {
    int t[N], n;
    void init (int x) { memset (t, 0, sizeof t); n = x; }
    int lowbit (int x) { return x & -x; }
    void add (int x, int k) { for (; x <= n; x += lowbit (x)) t[x] += k; }
    int sum (int x) { int ret = 0; for (; x;  x -= lowbit (x)) ret += t[x]; return ret; }
    int query (int l, int r) { return sum (r) - sum (l - 1); }
} t;

int R[N][30], son[N][30], fa[N], num[N], cnt, n, cor[N], num123[N];
int fail[N], ans[N];

stack <char> s;
vector <int> trie[N], failt[N];
vector < pair <int, int> > que[N];

void build () {
    queue <int> q;
    for (int i = 0; i < 26; i ++) if (son[0][i]) q.push (son[0][i]), failt[0].push_back (son[0][i]);
    // printf ("%d\n", q.size ());
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        for (int i = 0; i < 26; i ++) {
            int& v = son[u][i];
            if (v) fail[v] = son[ fail[u] ][i], q.push (v), failt[ son[ fail[u] ][i] ].push_back (v);
            else   v = son[ fail[u] ][i];
        }
    }
}

int dfn[N], L[N], Rr[N], tot;

void dfs_fail (int u) {
    L[u] = dfn[u] = ++ tot;
    for (auto v : failt[u])
        // printf ("%d -> %d (%c)\n", u, v, num123[v]),
        dfs_fail (v);
    Rr[u] = tot;
}

void dfs_trie (int u) {
    t.add (dfn[u], 1);
    // printf ("%d arrived at %d.\n", u, dfn[u]);

    for (auto [id, v] : que[u]) ans[id] += t.query (L[v], Rr[v]);

    for (int i = 0; i < 26; i ++)
        if (R[u][i]) {
            dfs_trie (son[u][i]);
        }
    t.add (dfn[u], -1);
}

int main (void) {

    int now = 0;
    char CNM[N]; scanf ("%s\n", CNM); 
    int l = strlen (CNM);

    for (int i = 0; i < l; i ++) {
        char ch = CNM[i]; 
        // printf ("%c", ch);
        if (ch == 'B') now = fa[now];
        else if (ch == 'P') ++ num[now], cor[++ n] = now;
        else {
            if (!son[now][ch - 'a']) son[now][ch - 'a'] = ++ cnt;
            trie[now].push_back (son[now][ch - 'a']);
            num123[ son[now][ch - 'a']] = ch;
            R[now][ch - 'a'] = true;
            fa[son[now][ch - 'a']] = now; 
            // printf ("%d\n", son[u][i])
            now = son[now][ch - 'a'];
            // printf ("%d\n", cnt);
        }
    }
    // printf ("%d\n", cnt);
    
    build ();
    dfs_fail (0);

    int m; scanf ("%d", &m);
    for (int i = 1, x, y; i <= m; i ++) scanf ("%d%d", &x, &y), que[ cor[y] ].push_back ({i, cor[x]});

    t.init (l);
    dfs_trie (0);

    for (int i = 1; i <= m; i ++) printf ("%d\n", ans[i]);

    return 0;
}