https://www.luogu.com.cn/problem/P3201
题目描述
nn 个布丁摆成一行，进行 mm 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。
例如，颜色分别为 1,2,2,11,2,2,1 的四个布丁一共有 33 段颜色.
输入格式
第一行是两个整数，分别表示布丁个数 nn 和操作次数 mm。
第二行有 nn 个整数，第 ii 个整数表示第 ii 个布丁的颜色 a_iai。
接下来 mm 行，每行描述一次操作。每行首先有一个整数 opop 表示操作类型：
- 若 op = 1op=1，则后有两个整数 x, yx,y，表示将颜色 xx 的布丁全部变成颜色 yy。
- 若 op = 2op=2，则表示一次询问。
输出格式
对于每次询问，输出一行一个整数表示答案。
输入输出样例
输入 #14 3 1 2 2 1 2 1 2 1 2输出 #1
3 1
说明/提示
样例 1 解释
初始时布丁颜色依次为 1, 2, 2, 11,2,2,1，三段颜色分别为 [1, 1], [2, 3], [4, 4][1,1],[2,3],[4,4]。
一次操作后，布丁的颜色变为 1, 1, 1, 11,1,1,1，只有 [1, 4][1,4] 一段颜色。
数据规模与约定
对于全部的测试点，保证 1 \leq n, m \leq 10^51≤n,m≤105，1 \leq a_i ,x, y \leq 10^61≤ai,x,y≤106。
提示
请注意，不保证颜色的编号不大于 nn，也不保证 x \neq yx=y，mm 不是颜色的编号上限。
分析
n 个操作，每次将 n 个数合并，直接操作的话是 n^2 ，但是每次把数量少的 颜色 合并到数量大的颜色，启发式操作是n logn
启发式操作：if(sz[x] < sz[y]) swap(x,y);p[y] = x;
然后用链表把 颜色内的元素串起来 ，每次合并操作的时候，改变元素较少的链表的所有元素，然后把它接到元素较多的颜色上去（新概念并查集）
注意到，如果当前颜色是x，要被改成 y ，如果颜色为x 的数量比 y 的数量多，会有一个问题，之后如果想修改颜色 y ，但是由于y 已经合并到 x 上了，会找不到 y ，这里定义一个 并查集数组f，
当出现这种情况的时候就交换 f，然后让各自链表合并
if(sz[f[x]] > sz[f[y]]) swap(f[x],f[y]);
#include <iostream>
#include <cstdio>
const int N=1e5+5,M=1e6+5;
int n,m,c[N],sz[M],st[M],f[M],hd[M],nxt[N],ans;
//链表
void merge(int x,int y) {
for(int i=hd[x];i;i=nxt[i]) ans-=(c[i-1]==y)+(c[i+1]==y);
for(int i=hd[x];i;i=nxt[i]) c[i]=y;
nxt[st[x]]=hd[y],hd[y]=hd[x],sz[y]+=sz[x];
hd[x]=st[x]=sz[x]=0;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&c[i]),f[c[i]]=c[i];
ans+=c[i]!=c[i-1];
if(!hd[c[i]]) st[c[i]]=i;
++sz[c[i]],nxt[i]=hd[c[i]],hd[c[i]]=i;
}
while(m--) {
int opt;
scanf("%d",&opt);
if(opt==2) printf("%d\n",ans);
else {
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
if(sz[f[x]]>sz[f[y]]) std::swap(f[x],f[y]);
if(!sz[f[x]]) continue;
merge(f[x],f[y]);
}
}
return 0;
}
标签：sz,颜色,int,布丁,链表,hd From： https://www.cnblogs.com/er007/p/16622870.html