P8026 ONTAK2015 Bajtocja

· · 题解

欢迎您到我的博客查看本文，谢谢！

题目只考察连通性，不考察图更具体的结构，所以可以用 d 个并查集维护。

两个点 u 和 v 在图 i 上连通，当且仅当图 i 上 u 和 v 的并查集祖先相同。

因此，两个点 u 和 v 在 d 张图上都连通，等价于对于任意 i，u 和 v 在第 i 张图的并查集祖先相同。

所以考虑对每个点 u 维护一个长度为 d 的字符串 s_u，s_u(i) 表示第 i 张图上 u 的并查集祖先。

于是 u 和 v 在 d 张图上连通等价于 s_u = s_v。

我们动态地维护这 n 个字符串的哈希值，对于哈希值相同的 k 个字符串，可以给答案贡献 k^2。开桶记录即可。

因为桶的下标是字符串哈希值域量级，桶用 unordered_map（如果会哈希表用哈希表也行）。

现在考虑动态维护 n 个字符串哈希值的复杂度。很明显，每次我们更改的字符串不能太多。

对于一次在第 k 张图连接 a 和 b 的操作，我们会修改 s_u 的第 k 个字符，其中 u 是所有这次连边中在并查集上被更改祖先的点。我们要控制这个点数的量级。

所以不路径压缩，考虑按并查集树的大小启发式合并。这样以来，一个点在第 d 张图中，被更改祖先的次数不会超过 \log n 次（因为被更改一次祖先，它所在的并查集树的大小就会翻倍），每个字符串被修改的数量不超过 d\log n，所有字符串被修改的总次数为 dn\log n 量级。

时间复杂度 \Theta(dn\log n)，常数略大。

另外这里所有字符串长度都是 d，所以可以不用写普通的字符串哈希，直接给每个位置随机一个权值 w(i)，记 S(i) 为字符串 S 的第 i 个字符，我们令 S 的哈希值为 \sum w(i) \times S(i) 即可。这样代码会更好写，而且规避了可能的卡哈希问题（本题好像把基数为 131 的自然溢出哈希卡了）。

typedef unsigned long long ull;

const int D = 205;
const int N = (int)5e3 + 5;

int rt[D][N];
std :: vector <int> t[D][N]; // t[k][u] 表示第 k 层图中以 u 为根的并查集树
ull ha[N], val[D];
int ans;
std :: unordered_map <ull, int> cnt;

inline void add(ull ha) {
    int x = cnt[ha];
    ans += 2 * x + 1;
    ++cnt[ha];
}

inline void del(ull ha) {
    int x = cnt[ha];
    ans -= 2 * x - 1;
    if (--cnt[ha] == 0)
        cnt.erase(ha); // 本题一个哈希值消失就很难再现，直接 erase 掉能显著减小常数。不 erase 也没什么问题。
}

int main() {
    int d = read(), n = read(), m = read();
    std :: mt19937_64 rng(std :: random_device{}());
    for (int i = 1; i <= d; ++i)
        val[i] = rng();
    for (int i = 1; i <= d; ++i) {
        for (int u = 1; u <= n; ++u) {
            rt[i][u] = u;
            ha[u] += u * val[i];
            t[i][u].push_back(u);
        }
    }

    for (int u = 1; u <= n; ++u)
        add(ha[u]);

    while (m--) {
        int u = read(), v = read(), k = read();
        u = rt[k][u]; v = rt[k][v];
        if (u == v) {
            printf("%d\n", ans);
            continue;
        }
        if (t[k][v].size() > t[k][u].size())
            std :: swap(u, v);
        for (int x : t[k][v]) {
            t[k][u].push_back(x);
            rt[k][x] = u;
            del(ha[x]);
            ha[x] += (u - v) * val[k];
            add(ha[x]);
        }
        t[k][v].clear();
        printf("%d\n", ans);
    }
    return 0;
}

如果您觉得我的题解写的不错，解决了您的疑惑的话，请给我题解点个赞，谢谢！