CF1209G Into Blocks

题意：给出一个长度为 的序列。

我们需要达成：如果存在 ，那么必须满足所有 都必须在序列中连续。

可以进行的操作：将所有的 的变为任意你指定的 ，并且花费 元素的个数的代价。

求达成目标的最小化费。有 次单点修改。

，时限 。

---

先来求达成目标的最小化费。

对于某种颜色 ，设其最左侧为 ，最右侧为 。

若最终要保留这种颜色，肯定要把 都染成 。

这样不难发现，若 有交集，那么 两种颜色肯定只能保留一个。

我们把有交集的区间并起来，每个并中保留众数即可。

---

接下来考虑动态维护。

修改一个位置，可能会导致两个区间变化。

对于每个区间 ，给 加一，则 为每个线段并区间的分界线（右侧）。

现在需要维护每两个 之间的区间众数出现次数和。

维护区间最左端的 和最右端的 ，合并时考虑跨越分界线的两个 。

实际实现中需要维护最左端和最右端的最小值，以及各个最小值之间的众数和。

每次合并区间时，需要查询一次区间众数。

一般的区间众数解法较为复杂，但是本题中保证所有可能作为答案的数都在询问区间内。

那么我们给 的任意一次出现赋值 ，众数就是区间最大值，这可以用另一棵线段树维护。

这能够做到 。

考虑在线段树上额外维护左端最小值到左边界的 ，右端最小值到右边界的 即可做到 。