启发式合并

upd:学了线段树合并之后回来，决定将两篇分开

关于启发式合并：

首先对于启发式算法的定义：

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

比如启发式搜索\(A^*\)算法。
至于启发式合并是什么，请先考虑一个问题：将\(n\)个元素个数为\(m\)的线性数据结构合并，求时间复杂度
如果用朴素算法合并，每次合并的最坏时间复杂度为\(O(m)\),\(n\)个元素合并的最坏时间复杂度为\(O(nm)\),属实是拉跨
考虑每次合并两个数据结构时，将个数少的合并到个数多的数据结构时的时间复杂度，即每次合并复杂度为\(O(\min(m_1,m_2))\)
似乎没啥软用？
如果注意到这样合并会产生一个性质：每次合并后个数为合并前少的部分的个数的两倍以上，所以每个元素最多被合并\(logn\)次（可以自己想想为啥），总时间复杂度也就变成\(O(nlogm)\)
同时，启发式合并也是很多高级算法的前置知识，比如线段树的合并，如果用启发式合并，可以将复杂度优化到\(mlog^2m\)(线段树合并小蒟蒻还不会，所以没写)
总而言之启发式合并核心思想就一句话：把小集合的合并到大的里。

模板题：

1、
洛谷 P3201 [HNOI2009] 梦幻布丁
链表+启发式合并
题意很容易理解，此处不在赘述。
其中的“将颜色\(x\)的布丁全部变成颜色\(y\)”操作可以抽象成一个合并过程。
因为数据范围是\(10^5\),虽然原始数据可以\(n^2\)过百万，但后来被卡了kk/
所以要考虑使用启发式合并。
对于题目中每一种颜色的元素，创造一个链表，每次染色操作就把标记为\(x\)的链合并到标记为\(y\)的链上（要判断一下，保证x是更短的链）。
注意一个细节：要开一个数组存储某个链表的当前颜色。
code

2、
洛谷 P5290 [十二省联考 2019] 春节十二响
配对堆+启发式合并
题意：有一个树，树上每个点带点权，现在将点划成若干个集合，要求每个集合里的点没有祖先后代关系，集合的权值是集合里点权最大的点的权值，求一个划分方案使所有集合权值总和最小。
做法：

• 由链的部分分可以发现，对于一条链可以直接对于左右各开一个堆，然后每次左右各弹一个取\(max\),我们思考怎么由链拓宽到树上。
• 以二叉树为例，它的每一个二叉可以看做一条链，左右两部分按照部分分的方式合并之后就变成了条新的链，链上每个点为之前两条“子链”的两个对应点的\(max\),然后递归的做下去就好了。
• 至于多叉树，显然和二叉树一样。

时间复杂度：

• 理论上的时间复杂度应为\(O(nlog^2n)\)，但是这道题的启发式合并与传统的启发式合并有所不同，实际上的时间复杂度为\(O(nlogn)\)
• 因为在合并的过程中，并没有“合并”进去，而是把小的那部分“贴”上去后直接把小的“丢掉了”，每个点只会被遍历一次
• 每弹出一个点的时间复杂度为\(O(logn)\),所以总时间复杂度为\(O(nlogn)\)

最后，不开long long见祖宗，数组开小见祖宗。
code