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

题目大意

n

个布丁摆成一行即

a_1, a_2, \cdots, a_n

，进行

m

次操作。每次可以某个颜色的布丁全部变成另一种颜色的或者询问当前一共有多少段颜色。

1 \le n, m \le 10^5, 1 \le a_i \le 10^6

分析

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

考虑启发式合并，我们可以将布丁少的颜色涂成布丁多的颜色，因为

x \to y

和

y \to x

本质是相同的，因为每次集合大小都会至少翻一倍，所以每个布丁至多只会被加入到其他集合

\log n

次，所以时间复杂度

\mathcal{O}(n \log n)

。

在维护的时候，可以用 set 维护此颜色的所有位置。在

x \to y

时，我们可以看所有

x

的位置两边是不是

y

。

code

CPP

#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;
}

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

文章操作

题目大意

分析

code

相关推荐

评论

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