题解 P2336 [SCOI2012] 喵星球上的点名

· · 题解

题目描述

有 N 只喵，每只喵有一个名和一个姓（两个字符串）。

还有 M 次点名（也是一个字符串），如果一只喵的名或姓中包含这个字符串，这只喵就会喊“到”。

有两问 :

  1. 对于每次点名询问有多少只喵喊“到”。

  2. 对于每一只喵问询她喊了多少次“到”。

字符集 |\Sigma| \le 10^4, 总字符串长不超过 2 \times 10^5。

正解

简单分析

先可以把一只喵的名和姓合并在一起，中间插入一个不存在的字符，这样就不需要考虑两个串了。

询问是类似于字符串 x 在字符串 y 中是否出现过。

如果字符串出现多次算多次的话，这里有一道用 AC 自动机 经典的例题。

考虑 AC 自动机 \text{fail} 树的性质，\text{fail} 指针指向的是最长相同后缀。

如果字符串 A 是字符串 B 的后缀, 那么在 AC 自动机上面，从 B 开始跳 \text{fail} 树，一定可以跳到 A。

也就是说，B 在 A 的子树内，A 是 B 的祖先。（在 \text{fail} 树上）

判断 A 是否在 B 中出现过，就可以对于 B 的每一个前缀（子串一定是一个前缀的后缀），在 \text{fail} 树上暴力往上跳进行修改或者查询即可。

但是暴力跳 \text{fail} 复杂度可能不太对，但是好像也可以通过此题，这里给出一个复杂度为 O(n \log n) 的做法。

第一问

对于一个名字串的每一个前缀（总前缀个数不超过字符串总长），覆盖它到根的路径（覆盖表示加多次算一次）。

对每一个名字串都这么做，看点名串总共被多少个名字串给覆盖。

树上链修改，单点查询的问题先转化成树上单点修改，子树查询的问题j。

由于覆盖多次算只算一次，就要把覆盖多的部分减掉。

这里有一个小 trick。

对名字串的前缀按 \text{dfs} 序排序，减掉的部分就是每相邻节点的 \text{lca}。

这样就可以做覆盖多次算一次了。

第二问

对于一个名字串的所有一个前缀，看它们总共覆盖了多少点名串。

树上单点修改，链查询的问题先转化串树上子树修改, 单点查询的问题。

同样利用上面的 trick，减掉 \text{dfs} 序相邻节点 \text{lca} 的贡献即可。

复杂度分析

询问都只需要用到排序和树状数组，这一部分复杂度为 O(n \log n)。

但是有一部分的复杂度很迷，就是 \text{trie} 树求 \text{fail} 的那一部分，求 \text{fail} 是暴力跳的（但好像复杂度均摊？），复杂度我也不敢下定论。

求哪位大佬帮忙证明一下复杂度，或者直接 hack 掉这种做法。

update :

字符集比较大的时候确实这样写确实不对的，无论是普通写法（将不存在的 \text{to} 指针设为 \text{fail} 的 \text{to} 指针），还是临时跳 \text{fail} 并且记忆化，最坏复杂度是 O(|\Sigma| \times N) 的，但是第二种写法可能远远达不到这个最坏复杂度，而且貌似最坏也就 10^9 ？，所以可以通过此题。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int S = (N + M) << 1;

int n, m;
int namePos[N], queryPos[M];

int last, vcnt = 0;
struct node {
    int fa, fail; // 此处的 fa 为 trie 树上的 fa
    map<int, int> to;
} a[S];

int que[S];
int siz[S], dep[S], son[S], fa[S]; // 此处的 fa 相当于 ac 自动机上的 fail
int dfn[S], top[S], dfc; 
vector<int> g[S];

namespace BIT {
#define lowbit(x) (x & -x)
    int c[S];
    void clear() { memset(c, 0, sizeof c); }
    void update(int p, int v) {
        for(int i = p; i <= dfc; i += lowbit(i))
            c[i] += v;
    }
    int sum(int p) {
        int res = 0;
        for(int i = p; i; i -= lowbit(i))
            res += c[i];
        return res;
    }
    int query(int l, int r) { return sum(r) - sum(l - 1); }
#undef lowbit
} // namespace BIT

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

void extend(int c) {
    int &v = a[last].to[c];
    if(!v) v = ++vcnt, a[v].fa = last;
    last = v;
}

int getFail(int u, int c) {
    if(a[u].to.count(c)) return a[u].to[c];
    else if(!u) return u;
    return a[u].to[c] = getFail(a[u].fail, c);
}

void buildFailTree() {
    int hd = 1, tl = 0;
    for(auto pr : a[0].to)
        que[++tl] = pr.second;
    while(hd <= tl) {
        int u = que[hd++];
        for(auto pr : a[u].to) {
            a[pr.second].fail = getFail(a[u].fail, pr.first);
            que[++tl] = pr.second;
        }
    }
    for(int i = 1; i <= vcnt; ++i)
        g[a[i].fail].push_back(i);
}

void preDfs(int u) {
    siz[u] = 1;
    dfn[u] = ++dfc;
    dep[u] = dep[fa[u]] + 1;
    for(int v : g[u]) if(v != fa[u]) {
        fa[v] = u, preDfs(v);
        siz[u] += siz[v];
        if(!son[u] || siz[v] > siz[son[u]])
            son[u] = v;
    }
}
void getTop(int u, int tp) {
    top[u] = tp;
    if(son[u]) getTop(son[u], tp);
    for(int v : g[u]) if(v != fa[u] && v != son[u]) {
        getTop(v, v); 
    }
}

inline int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int arr[N], tot;
bool cmp(const int &u, const int &v) { return dfn[u] < dfn[v]; }

void solve1() {
    BIT::clear();
    for(int i = 1, u; i <= n; ++i) {
        u = namePos[i], tot = 0;
        while(u) {
            arr[++tot] = u;
            BIT::update(dfn[u], 1);
            u = a[u].fa;
        }
        sort(arr + 1, arr + tot + 1, cmp);
        for(int j = 1; j < tot; ++j)
            BIT::update(dfn[lca(arr[j], arr[j + 1])], -1);
    }
    for(int i = 1, u; i <= m; ++i) {
        u = queryPos[i];
        printf("%d\n", BIT::query(dfn[u], dfn[u] + siz[u] - 1));
    }
}
void solve2() {
    BIT::clear();
    for(int i = 1, u; i <= m; ++i) {
        u = queryPos[i];
        BIT::update(dfn[u], 1);
        BIT::update(dfn[u] + siz[u], -1);
    }
    for(int i = 1, u, res; i <= n; ++i) {
        u = namePos[i], tot = 0, res = 0;
        while(u) {
            arr[++tot] = u;
            res += BIT::sum(dfn[u]);
            u = a[u].fa;
        }
        sort(arr + 1, arr + tot + 1, cmp);
        for(int j = 1; j < tot; ++j)
            res -= BIT::sum(dfn[lca(arr[j], arr[j + 1])]);
        printf("%d%c", res, " \n"[i == n]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P2336.in", "r", stdin);
    freopen("P2336.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1, l, c; i <= n; ++i) {
        last = 0;
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        } extend(-1);
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        }
        namePos[i] = last;
    }
    for(int i = 1, l, c; i <= m; ++i) {
        last = 0;
        l = read();
        for(int j = 1; j <= l; ++j) {
            c = read();
            extend(c);
        }
        queryPos[i] = last;
    }

    buildFailTree();

    preDfs(0);
    getTop(0, 0);

    solve1();
    solve2();
    return 0;
}