BZOJ1483[HNOI2009]梦幻布丁

@(BZOJ)[启发式合并]

题面

Description

N个布丁摆成一行,进行M次操作.
每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.
例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

Input

第一行给出N,M表示布丁的个数和好友的操作次数。
第二行N个数A1,A2...AN表示第i个布丁的颜色。
从第三行起有M行，对于每个操作，若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y。若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数0。

Output

针对第二类操作即询问，依次输出当前有多少段颜色。

Sample Input

Sample Output

3
1

HINT

1≤n,m≤100,000;0<Ai,x,y<1,000,000

题目大意

给定一个序列, 每个点代表一种颜色. 有两种操作:

询问不同颜色组成的颜色段的数量
将一种颜色的所有点改成另外一种颜色

Solution

启发式合并链表.
我们用一个链表来记录每一种颜色的出现位置(链表所记录的位置不要求具有单调性).
对于最开始的序列, 我们将其统计好答案. 对于后面的修改((x, y)), 启发式合并两种颜色所在的链表. 具体操作有:

(O(1))将较小的链表链接到较大的链表上. 用mp[]数组记录交换后的颜色情况.
(Oleft( min(sz_x, sz_y) ight))统计答案

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

const int N = (int)1e5, LIM = (int)1e6;
int a[N + 1], ans, mp[LIM + 1];

namespace Zeonfai
{
	inline int getInt()
	{
		int a = 0, sgn = 1;
		char c;

		while(! isdigit(c = getchar()))
			if(c == '-')
				sgn *= -1;

		while(isdigit(c))
			a = a * 10 + c - '0', c = getchar();

		return a * sgn;
	}
}

struct lists
{
	struct node
	{
		int pos, nxt;
	}nd[N];

	int hd[LIM + 1], tp, sz[LIM + 1];

	inline void initialize()
	{
		memset(hd, -1, sizeof(hd));
		memset(sz, 0, sizeof(sz));
		tp = 0;
	}

	inline void addNode(int a, int pos)
	{
		nd[tp].pos = pos, nd[tp].nxt = hd[a];
		hd[a] = tp ++;
		++ sz[a];
	}

	inline void merge(int x, int y)
	{
		if(x == y)
			return;
		
		if(sz[mp[x]] > sz[mp[y]])
			std::swap(mp[x], mp[y]);
		
		x = mp[x], y = mp[y];
		
		if(! sz[x]) 
			return;

		for(int p = hd[x]; ~ p; p = nd[p].nxt)
		{
			if(a[nd[p].pos - 1] == y)
				-- ans;

			if(a[nd[p].pos + 1] == y)
				-- ans;
		}

		int p;
		
		for(p = hd[x]; ; p = nd[p].nxt)
		{
			a[nd[p].pos] = y;
			
			if(nd[p].nxt == -1)
				break;
		}

		nd[p].nxt = hd[y], hd[y] = hd[x], hd[x] = -1;
		sz[y] += sz[x], sz[x] = 0;
	}
}lst;

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("my.out", "w", stdout);
	#endif

	using namespace Zeonfai;

	int n = getInt(), m = getInt();
	lst.initialize();

	for(int i = 1; i <= n; ++ i)
	{
		a[i] = getInt();

		if(a[i] ^ a[i - 1])
			++ ans;

		lst.addNode(a[i], i);
		mp[a[i]] = a[i];
	}

	for(int i = 1; i <= m; ++ i)
	{
		int opt = getInt();

		if(opt == 1)
		{
			int x = getInt(), y = getInt();
			lst.merge(x, y);
		}
		else
			printf("%d
", ans);
	}
}