启发式算法是什么？
启发式算法是基于人类的经验和直观感觉，对一些算法的优化。
比如说启发式搜索\(A\)*算法。
启发式合并是什么？
考虑一个问题：把\(n\)个总元素个数为\(m\)的数据结构合并起来（假设是线性的）。
每次合并复杂度最坏\(O(m)\)，总复杂度\(O(nm)\)？显然无法接受。
每次把个数少的合并到个数多的？复杂度\(O(min(m_1, m_2))\)
好像没啥用？
可是我们注意到，每次合并后个数为合并前少的部分的个数的两倍以上，每个元素最多合并\(logm\)次，总复杂度\(O(mlogm)\)。
我们也可以启发式合并更加高级的数据结构，如\(heap\)，\(set\)，\(splay\)等，复杂度\(O(mlog^2m)\)
很玄学？但这个复杂度分析是对的，而且跑的也快。
例题：HNOI2009 梦幻布丁
题意就不赘述了。
对于每一个颜色，建一条链表。然后染色就是把链短的合并到链长的。
需要注意细节，如果把\(2\)染成\(3\)，但\(2\)的链比\(3\)的长，就需要把\(3\)的合并到\(2\)上。但是现在本应属于\(3\)的链在\(2\)上，就需要记一个该颜色的链现在在哪个颜色上，即是代码中的\(now\)数组。
#include<cstdio> #define rep(i, a, b) for (register int i=(a); i<=(b); ++i) #define per(i, a, b) for (register int i=(a); i>=(b); --i) using namespace std; void swap(int &x, int &y){x^=y^=x^=y;} const int N=1000005; int head[N], nxt[N], col[N], now[N], cnt[N], st[N], ans; inline int read() { int x=0,f=1;char ch=getchar(); for (;ch<\'0\'||ch>\'9\';ch=getchar()) if (ch==\'-\') f=-1; for (;ch>=\'0\'&&ch<=\'9\';ch=getchar()) x=(x<<1)+(x<<3)+ch-\'0\'; return x*f; } void merge(int x, int y) { cnt[y]+=cnt[x]; cnt[x]=0; for (int i=head[x]; i; i=nxt[i]) { if (col[i+1]==y) ans--; if (col[i-1]==y) ans--; } for (int i=head[x]; i; i=nxt[i]) col[i]=y; nxt[st[x]]=head[y]; head[y]=head[x]; head[x]=st[x]=cnt[x]=0; } int main() { int n=read(), m=read(); rep(i, 1, n) { col[i]=read(); now[col[i]]=col[i]; if (col[i]^col[i-1]) ans++; if (!head[col[i]]) st[col[i]]=i; cnt[col[i]]++; nxt[i]=head[col[i]]; head[col[i]]=i; } rep(i, 1, m) { int opt=read(); if (opt==2) printf("%d\n", ans); else { int x=read(), y=read(); if (x==y) continue; if (cnt[now[x]]>cnt[now[y]]) swap(now[x], now[y]); x=now[x]; y=now[y]; if (cnt[x]) merge(x, y); } } return 0; }在看一道新鲜出炉的联考题：春节十二响
题意比较复杂，自己看吧$QAQ $。
考虑链的部分分做法，将两条支链分别排序，然后从大到小加上两边的\(max\)即可。
那么我们就有了一个暴力做法。对每个点维护一个堆，每次像链那样暴力合并即可，复杂度大概是\(O(n^2logn)\)？
改成启发式合并就可以了，每次把小的堆合并到大的堆上。时间复杂度\(O(nlog^2n)\)，其实跑的很快。
#include<cstdio> #include<vector> #include<queue> #define rep(i, a, b) for (register int i=(a); i<=(b); ++i) #define per(i, a, b) for (register int i=(a); i>=(b); --i) using namespace std; const int N=200005; vector<int> G[N], Q; priority_queue<int> q[N]; int val[N], id[N], n; long long ans; inline int read() { int x=0,f=1;char ch=getchar(); for (;ch<\'0\'||ch>\'9\';ch=getchar()) if (ch==\'-\') f=-1; for (;ch>=\'0\'&&ch<=\'9\';ch=getchar()) x=(x<<1)+(x<<3)+ch-\'0\'; return x*f; } void dfs(int u) { for (int v: G[u]) { dfs(v); if (q[id[u]].size()<q[id[v]].size()) swap(id[u], id[v]); int s=q[id[v]].size(); Q.clear(); rep(i, 1, s) { Q.push_back(max(q[id[u]].top(), q[id[v]].top())); q[id[u]].pop(); q[id[v]].pop(); } for (int i:Q) q[id[u]].push(i); } q[id[u]].push(val[u]); } int main() { n=read(); rep(i, 1, n) val[i]=read(), id[i]=i; rep(i, 2, n) G[read()].push_back(i); dfs(1); while (!q[id[1]].empty()) ans+=q[id[1]].top(), q[id[1]].pop(); printf("%lld\n", ans); return 0; }本来这里还有一个题，经提醒并不是启发式合并，故删去