背景介绍

首先见名知意：启发式合并是一种合并算法，它也属于启发式算法之一。
启发式算法：基于人类的直觉和感观，想出来的对某些算法的优化。

介绍复杂度

启发式合并常用于优化一些高级的数据结构：并查集、树、链表、队列等

举个例子：
    如果让我们合并这两个集合[3, 2, 1, 5]和[8, 9, 10],我们肯定会去遍历更小的集合的每个元素。
这么看来有点像暴力，但是如果分析一下每个元素被便利的次数就有意外发现。
我们每次合并的对象是两个集合或者两棵树等等，我们可用size_a和size_b表示两者的大小或树高等信息。
我们不妨认为size_a < size_b,那么两者合并之后的size一定大于等于size_a的两倍,
所以说每个元素最多被遍历log2(n)次

梦幻布丁{:target=”_blank”}

优化链表

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;

int head[N], ne[N], col[N], f_col[N], fa[N], sz[N];
int n, m;
int ans;

void Init()
{
    memset(head, -1, sizeof head);
}

void merge(int x, int y)
{
    for (int i = head[x]; i != -1; i = ne[i])
    {
        if (col[i - 1] == y)
            ans--;
        if (col[i + 1] == y)
            ans--;
    }
    for (int i = head[x]; i != -1; i = ne[i])
        col[i] = y;
    ne[fa[x]] = head[y];
    head[y] = head[x];
    sz[y] += sz[x];
    head[x] = sz[x] = fa[x] = 0;
}

int main()
{
    Init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &col[i]);
        if (col[i] != col[i - 1])
            ans++;
        f_col[col[i]] = col[i];
        if (head[col[i]] == -1)
            fa[col[i]] = i;
        sz[col[i]]++;
        ne[i] = head[col[i]];
        head[col[i]] = i;
    }
    int op;
    while (m--)
    {
        scanf("%d", &op);
        if (op == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x == y)
                continue;
            if (sz[f_col[x]] > sz[f_col[y]])
                swap(f_col[x], f_col[y]);
            x = f_col[x], y = f_col[y];
            if (!sz[x])
                continue;
            merge(x, y);
        }
        else
            printf("%d\n", ans);
    }

    return 0;
}