【启发式合并】题解：P3201 [HNOI2009] 梦幻布丁

ljk8886 · 2025-09-06 17:32:05 · 题解

题目传送门

题目大意

分析

暴力修改很容易想到，但复杂度爆炸。

考虑启发式合并，我们可以将布丁少的颜色涂成布丁多的颜色，因为 x \to y 和 y \to x 本质是相同的，因为每次集合大小都会至少翻一倍，所以每个布丁至多只会被加入到其他集合 \log n 次，所以时间复杂度 \mathcal{O}(n \log n)。

在维护的时候，可以用 set 维护此颜色的所有位置。在 x \to y 时，我们可以看所有 x 的位置两边是不是 y。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
    ll res = 0, f = 1; char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e5 + 5, A = 1e6 + 5;
int a[N];
set<int> st[A]; 
int main()
{
    int n = read(), m = read();
    int ans = 0;
    for (int i = 1; i <= n; i++) st[a[i] = read()].insert(i), ans += (a[i] != a[i - 1]);
    while (m--)
    {
        int opt = read();
        if (opt == 1)
        {
            int x = read(), y = read();
            if (x == y) continue;
            if (st[x].size() > st[y].size()) swap(st[x], st[y]);
            // x -> y
            for (int i : st[x]) ans -= (st[y].count(i - 1) + st[y].count(i + 1));
            // 如果颜色 x 的左右两边有颜色 y
            for (int i : st[x]) st[y].insert(i);
            // color x -> color y
            st[x].clear();
            // null -> color x + color y 
        }
        else writech(ans, '\n');
    }
    return 0;
}