启发式合并
类似并查集的按秩合并
- -
| ↓| ↓
o o o o o
暴力合并:
1+2+3+...n-1
O(n^2) 每次合并都遍历一遍之前所有的点
-> O(nlogn) 每次把元素所在的集合进行合并
则每次合并之后所在集合元素个数 >= 原个数 * 2
则每个元素最多合并logn次
颜色x -> 颜色y
合并颜色x和颜色y布丁
o o . o o o
| |
。贡献2段
.->o
少掉2段
一般化:
枚举所有要变的颜色x的布丁
左右两边的布丁是不是y
如果左边是y 段数-1
如果右边是y 段数-1
→
所有颜色 1 2 3 ... m
↓ ↓ ↓
颜色对应的编号 1 2 3 ... m
| |
o o
|
o
由于我们合并的原则是少的并到多的,本来想把1合并到2里变成把2合并到1里
所以要把颜色对应的编号指向1
→
所有颜色 1 2 3 ... m
↙↘ ↓
颜色对应的编号 1 2 3 ... m
|
o
|
o
|
o
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int h[M], e[N], ne[N], idx;//节点
int color[N], sz[M], p[M];//颜色,每种颜色的节点个数,每种颜色对应到哪个编号
int ans;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
sz[a] ++ ;
}
void merge(int& x, int& y)
{
if (x == y) return;
//本来要存在p[y]里,但因为sz[y]<sz[x] 所以存在p[x]里, 则传进来的p[x] p[y] 通过swap交换指向
if (sz[x] > sz[y]) swap(x, y);
// x为x,y中少的 , 遍历颜色为p[x]链表下的点 判断其相邻颜色 计算变换颜色后的段数
for (int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
ans -= (color[j - 1] == y) + (color[j + 1] == y);
}
for (int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
color[j] = y;//把p[x]这一条链上节点的颜色改为y
if (ne[i] == -1)
{
//走到p[x]的尾节点时 p[x]尾节点ne[p[x]的尾]接y头节点h[y] , p[y]头节点 h[p[y]]接x头节点h[p[x]]
ne[i] = h[y], h[y] = h[x];
break;
}
}
h[x] = -1;//并把原来的x链清空
sz[y] += sz[x], sz[x] = 0;
}
int main()
{
scanf("%d%d", &n, &m);// 布丁个数,操作个数
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &color[i]);
if (color[i] != color[i - 1]) ans ++ ;//当前颜色和前一个颜色不同 段数+1 第一个颜色不用特判
add(color[i], i);// 把当前布丁挂到颜色i的下面
}
// 初始时映射关系i->i
for (int i = 0; i < M; i ++ ) p[i] = i;
while (m -- )
{
int op;
scanf("%d", &op);
if (op == 2) printf("%d\n", ans);
else
{
int x, y;
scanf("%d%d", &x, &y);
merge(p[x], p[y]);
}
}
return 0;
}