洛谷P2414 [NOI2011] 阿狸的打字机题解

题目链接：P2414 [NOI2011] 阿狸的打字机

题意：

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

输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。

按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入 aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x,y)$（其中 $1\leq x,y\leq n$），打字机会显示第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

输入格式：

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数 $m$，表示询问个数。

接下来 $m$ 行描述所有由小键盘输入的询问。其中第 $i$ 行包含两个整数 $x, y$，表示第 $i$ 个询问为 $(x, y)$。

输出格式：

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

数据范围：

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq m\leq10^5$，第一行总长度 $\leq 10^5$。

~~不得了啦，这道题居然没有写！！~~

首先这个输入的方式，就差点把 Trie 写在题目里了，很方便建 Trie ！（大雾）

然后把 AC 自动机建出来，再把 Fail 树也给建出来，注意不要搞混了这俩的对应关系

那么对于询问 $(x,y)$ ，当 $y$ 固定时，答案就是 $y$ 在 Trie 上的每个节点在 Fail 树到根的路径上是否有 $x$

直接跳肯定是不行滴！但是我们发现 Trie 中能产生贡献的节点，在 Fail 树上一定在 $x$ 的子树内

那么就很简单了，我们离线处理所有的询问，把 $y$ 相同的放在一块处理

然后 dfs 一下 Trie ，一边走一边标记节点，碰到询问就查树状数组（子树查询参考树链剖分）

时间复杂度 $\mathcal{O}\left(26\sum |s_i| + q \log \left(\sum |s_i|\right)\right)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define Fi first
#define Se second

int n, a[N], dfn[N], sz[N], ans[N]; pii qry[N];
char s[N]; queue<int> q; vector<int> vec[N], ask[N];
int tot, trie[N][26], ok[N][26], fail[N], ed[N], fa[N], tr[N];
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= tot + 1; i += lowbit(i)) tr[i] += v; }
int sum(int x, int r = 0) { for(int i = x; i >= 1; i -= lowbit(i)) r += tr[i]; return r; }
void build()
{
    for(int i = 0; i < 26; i++) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = 0; i < 26; i++)
            if(trie[u][i])
            {
                fail[trie[u][i]] = trie[fail[u]][i];
                q.push(trie[u][i]);
            }else { trie[u][i] = trie[fail[u]][i]; }
    }
}
void dfs(int u)
{
    static int tim = 0; dfn[u] = ++tim; sz[u] = 1;
    for(int v : vec[u]) { dfs(v), sz[u] += sz[v]; }
}
void work(int u)
{
    add(dfn[u], 1);
    for(int id : ask[u])
    {
        int v = a[qry[id].Fi];
        ans[id] = sum(dfn[v] + sz[v] - 1) - sum(dfn[v] - 1);
    }
    for(int i = 0; i < 26; i++) if(ok[u][i]) work(ok[u][i]);
    add(dfn[u], -1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); int p = 0;
    for(int i = 1; s[i]; i++)
    {
        if(islower(s[i])) {
            int c = s[i] - 'a';
            if(!trie[p][c]) { trie[p][c] = ++tot, fa[tot] = p; }
            p = trie[p][c];
        }
        else if(s[i] == 'P') { ed[p] = ++n; a[n] = p; }
        else if(s[i] == 'B') { p = fa[p]; }
    }
    memcpy(ok, trie, sizeof(trie)); build(); 
    for(int i = 1; i <= tot; i++) vec[fail[i]].push_back(i);
    dfs(0); int qwq; cin >> qwq;
    for(int i = 1; i <= qwq; i++)
    {
        cin >> qry[i].Fi >> qry[i].Se;
        ask[a[qry[i].Se]].push_back(i);
    }
    work(0);
    for(int i = 1; i <= qwq; i++) cout << ans[i] << '\n';
    return 0;
}