布丁

[HNOI2009] 梦幻布丁 题目描述 $n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色. 输入格式 第一行是两个整数，分别表示布丁个数 $n$ 和操作次 ......

[HNOI2009] 梦幻布丁 题目描述 \(n\) 个布丁摆成一行，进行 \(m\) 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 \(1,2,2,1\) 的四个布丁一共有 \(3\) 段颜色. 数据范围 对于全部的测试点，保证 \(1 \l ......

[HNOI2009] 梦幻布丁 一种很暴力，很容易想到，但时间复杂度不对的做法： 既然每一次修改是以颜色作为单位的，那就用set或者链表(vector)维护每一个颜色出现的位置。将颜色\(x\)改为\(y\)的时候，遍历\(list_x\)的每一个点，判断其左右是否为\(y\)，更新ans(不同颜色 ......

# [2154. 梦幻布丁](https://www.acwing.com/problem/content/2156/) 考虑先维护连续段数。 我们可以先搞几个单链表，每个单链表存储的是每种颜色处于的所有位置，由于连续段数等于相邻两数不同的个数，我们可以先算出初始的情况，然后对于每次修改，暴力的将一 ......

Link 启发式合并是针对n个集合（总元素个数是O(n))的合并操作，每次将小的集合合并到大的集合 复杂度证明： 考虑每一个元素$$e \in E$$的贡献，如果在某一次合并中该元素被移动，那么集合的大小至少是$$2|E|$$，故复杂度是$$O(nlogn)$$ 具体的题目而言，我们可以看出对于$$ ......