P3201 [HNOI2009] 梦幻布丁 启发式合并，时间复杂度

[HNOI2009] 梦幻布丁

一种很暴力，很容易想到，但时间复杂度不对的做法：

既然每一次修改是以颜色作为单位的，那就用set或者链表(vector)维护每一个颜色出现的位置。将颜色\(x\)改为\(y\)的时候，遍历\(list_x\)的每一个点，判断其左右是否为\(y\)，更新ans(不同颜色块数量)

时间复杂度最大为 \(O(n^2)\)

合并问题，考虑“按秩合并”。

直观感觉就是每次把小区间合并到大区间上面去，这样每一次遍历 \(list_x\) 的时间就变少了。

证明如下：

每一次小区间合并到大区间，区间长度至少\(\times 2\)，所以每一个点在合并时被更新的次数不会超过 \(\log n\).总时间复杂度为\(O(n \log n)\)

细节问题：

因为是按秩合并，所以可能会把题目中的\(x\)颜色变为\(y\)操作成将\(y\)合并进\(x\).

所以小区间合并到大区间的时候，大区间表示的颜色要改变。具体用一个 \(f\) 数组记录一下即可。