【BZOJ1483】【HNOI2009】梦幻布丁（启发式合并，平衡树）

【BZOJ1483】【HNOI2009】梦幻布丁

题面

题目描述

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

输入格式：

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

输出格式：

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

输入样例#1：

4 3

1 2 2 1

2

1 2 1

2

输出样例#1：

3

1

说明

1<=n,m<=1,000,000; 0<Ai,x,y<1,000,000

题解

最近我做题用STL水上了瘾？？？其实是不想手打平衡树

直接用平衡树记录每一个颜色的位置

每次修改颜色的时候直接启发式合并

并且在合并的过程中查找前驱后继

检查是否合并成了一段，并且修改答案

每次询问直接输出

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

using namespace std;

#define MAX 1010000

set<int> S[MAX];

int N,M;

int A[MAX];

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int tot=0;

int ff[MAX];

void Merge(int x,int y)//把x合并到y

{

	set<int>::iterator t;

	for(t=S[x].begin();t!=S[x].end();t++)

	{

		int gg=*t;

		if(A[gg-1]==y)--tot;

		if(A[gg+1]==y)--tot;

	}

	for(t=S[x].begin();t!=S[x].end();t++)

		A[*t]=y,S[y].insert(*t);

	S[x].clear();

}

int main()

{

	N=read();M=read();

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

	{

		A[i]=read();

		if(A[i]!=A[i-1])tot++;

		S[A[i]].insert(i);

		ff[A[i]]=A[i];

	}

	while(M--)

	{

		int opt=read();

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

		else

		{

			int x=read(),y=read();

			if(ff[x]==ff[y])continue;

			if(S[ff[x]].size()>S[ff[y]].size())swap(ff[x],ff[y]);

			Merge(ff[x],ff[y]);

		}

	}

	return 0;

}