1483: [HNOI2009]梦幻布丁

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 4022  Solved: 1640
[Submit][Status][Discuss]

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。
n,m<=1000000

Output

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

Sample Input

4 3
1 2 2 1
2
1 2 1
2

Sample Output

3
1
 
/*
vector 记录每个颜色出现的位置
修改时启发式合并,更细答案即可。
*/
#include<bits/stdc++.h> #define N 1000007
#define inf 0x3f3f3f3f
#define ll long long using namespace std;
vector<int>v[N];
vector<int>::iterator it;
int n,m;
int fa[N],a[N]; int main()
{
scanf("%d%d",&n,&m);
int ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=a[i-])ans++;
fa[a[i]]=a[i];
v[a[i]].push_back(i);
}
while(m--)
{
int t;
scanf("%d",&t);
if(t==) printf("%d\n",ans);
else
{
int x,z;
scanf("%d%d",&x,&z);
if(x==z)continue;
if(v[fa[x]].size()>v[fa[z]].size()) swap(fa[x],fa[z]);
int col1=fa[x],col2=fa[z];
for(int i=;i<v[col1].size();i++)
{
v[col2].push_back(v[col1][i]);
if(a[v[col1][i]-]==col2) ans--;
if(a[v[col1][i]+]==col2) ans--;
}
for(int i=;i!=v[col1].size();i++) a[v[col1][i]]=col2;
v[col1].clear();
}
}
return ;
}
05-11 20:44