洛谷P5840 [COCI2015]Divljak 题解

题目链接：P5840 [COCI2015]Divljak

题意：

Alice 有 $n$ 个字符串 ${S}_1, {S}_2, \ldots, {S}_n$，Bob 有一个字符串集合 ${T}$，一开始集合是空的。

接下来会发生 $q$ 个操作，操作有两种形式：

1 P：Bob 往自己的集合里添加了一个字符串 ${P}$。

2 x：Alice 询问 Bob，集合 ${T}$ 中有多少个字符串包含串 ${S}_x$（我们称串 ${A}$ 包含串 ${B}$，当且仅当 ${B}$ 是 ${A}$ 的子串）。

输入格式：

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行一个字符串 ${S}_i$。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行一个操作。

输出格式：

对每个 2 x 操作，一行一个整数，表示答案。

数据范围：

$1 \leq n,q \leq 10^5$，字符串由小写字母构成，$S$ 和 $P$ 的总长分别 $\le 2 \times 10^6$。

这题显然跟多模式串匹配有关，发现最好建 AC 自动姬的就是 $S_1,S_2,\cdots,S_n$ 了，尝试以这个方向入手。

考察在 $T$ 中加入一个新的串 $P$ 会对 $S$ 产生怎样的贡献，记 $r_1,r_2,\cdots,r_l$ 为 $P$ 在 AC 自动姬上走过的节点

容易发现，$r_i$ 到 Fail Tree 根节点路径上的每个节点（所代表的串）都是 $P$ 的子串。

因此所有得到 $P$ 贡献的节点就是 $r_i$ 到根节点路径的节点的并，问题就转化为了树上求并。

树上求并可以通过以下办法计算：先将 $r_i$ 按 Fail Tree 的 dfn 序排序，然后我们做一个树上差分。

具体地，将每个 $r_i$ 增加 $1$ ，然后将 $\operatorname{LCA}(r_i,r_{i+1})$ 增加 $-1$ 。这个可以轻松地用树状数组维护。

时间复杂度 $\mathcal{O}(\sum |S_i| \log \sum |S_i| + \sum |P_i|)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
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)(2e6 + 15))

namespace Trie
{
    queue<int> q; signed tot = 1,fail[N],ed[N],trie[N][26];
    void insert(char *s)
    {
        int u = 1; static int tim = 0;
        for(int i = 1, c; s[i]; i++)
        {
            c = s[i] - 'a';
            if(!trie[u][c]) trie[u][c] = ++tot;
            u = trie[u][c];
        }
        ed[++tim] = u;
    }
    void build()
    {
        fail[1] = 0; q.push(1);
        for(int i = 0; i < 26; i++) trie[0][i] = 1;
        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];
            }
        }
    }
}using namespace Trie; 
char s[N]; vector<int> vec[N];
int n,Q,r[N],dfn[N],sz[N],dep[N],fa[N],son[N],tree[N],top[N];
void dfs(int u,int f,int d)
{
    fa[u] = f; dep[u] = d + 1; sz[u] = 1; int mx = -1;
    for(int v : vec[u])
    {
        if(v == f) continue;
        dfs(v,u,d+1); sz[u] += sz[v];
        if(sz[v] > mx) { mx = sz[v], son[u] = v; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; dfn[u] = ++tim; top[u] = ftop;
    if(son[u]) dfs(son[u], ftop);
    for(int v : vec[u]) {
        if(v != fa[u] && v != son[u]) dfs(v,v);
    }
}
int lca(int x,int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
#define lowbit(x) ((x) & (-(x)))
void add(int x,int v) { for(int i = x; i && i <= tot; i += lowbit(i)) tree[i] += v; }
int sum(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) { cin >> (s + 1); insert(s); }
    build(); cin >> Q;
    for(int i = 2; i <= tot; i++) vec[fail[i]].push_back(i);
    dfs(1,0,1); dfs(1,1);
    // for(int i = 1; i <= tot; i++) cout << fail[i] << " \n"[i == tot];
    for(int op,t,p,l; Q--; )
    {
        if(cin >> op, op == 1)
        {
            cin >> (s + 1); p = 1; l = strlen(s + 1);
            for(int i = 1, c; i <= l; i++) {
                c = s[i] - 'a'; p = trie[p][c]; r[i] = p;
            }
            // for(int i = 1; i <= l; i++) cout << r[i] << ' ';
            sort(r + 1, r + 1 + l, [](int a,int b){ return dfn[a] < dfn[b]; });
            for(int i = 1; i <= l; i++) add(dfn[r[i]], 1);
            for(int i = 1; i < l; i++) add(dfn[lca(r[i], r[i + 1])], -1);
        }else
        {
            cin >> t; p = ed[t];
            // cout << dfn[p] + sz[p] - 1 << ' ' << dfn[p] - 1 << '\n';
            cout << (sum(dfn[p] + sz[p] - 1) - sum(dfn[p] - 1)) << '\n';
        }
    }
    return 0;
}