HNOI2009 梦幻布丁

wjh15101051's space

卧薪尝胆，厚积薄发。

HNOI2009 梦幻布丁

Date: Tue Oct 02 21:03:27 CST 2018

In Category: NoCategory

Description：

$N$ 个布丁摆成一行，进行 $M$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。

$1\leqslant n\leqslant10^5$

Solution：

用 $set$ 来维护每个颜色的位置，修改颜色要么只影响了颜色，要么合并了两个集合，用启发式合并即可，在合并时顺便看一看有没有合并的块。

~~然而这题暴力合并就能过。~~

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<set>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int c[MAXN];

map<int,set<int> > s;

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&c[i]);

	int ans = n;

	for(int i = 1;i <= n;++i)

	{

		s[c[i]].insert(i);

		if(i != 1 && c[i] == c[i - 1])--ans;

	}

	int opt,x,y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 2)printf("%d\n",ans);

		else

		{

			scanf("%d%d",&x,&y);

			if(x == y)continue; 

			if(s.find(y) == s.end())

			{

				s[y] = s[x];

				s.erase(s.find(x));

			}

			else

			{

				for(set<int>::iterator it = s[x].begin();it != s[x].end();++it)

				{

					if(*it != n && s[y].find(*it + 1) != s[y].end())--ans;

					if(*it != 1 && s[y].find(*it - 1) != s[y].end())--ans;

				}

				for(set<int>::iterator it = s[x].begin();it != s[x].end();++it)

				{

					s[y].insert(*it);

				}

				s.erase(s.find(x));

			}

		}

	}

	return 0;

}

In tag: 数据结构-启发式合并 STL-set

wjh15101051