洛谷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;
}