Luogu4690 [Ynoi2016] 镜中的昆虫

题意 ： 维护长度为 的序列 ，支持：

• 区间覆盖

• 区间数颜色

允许离线，，时限 ，空限 。

---

先离散化一手。

回忆区间数颜色的经典套路，维护 表示 上一次出现的位置，然后区间 的答案即为 ：

这是二维数点。

考虑如何在区间覆盖的同时维护 。

使用 ODT 维护，会产生 次颜色连续段的修改。

每一个颜色连续段除了第一个位置之外，其余的 均为 。分两部分维护。

第一部分是颜色连续段的第一个位置。我们除了用一个 set 维护连续段，还要用 个 set 维护每种颜色，这样才能 求一个 。

求答案时是动态二维偏序问题，容易转为静态三维偏序，然后用 分治解决。

对于其余 的点，只有 可能有贡献，单独判一下即可。

复杂度 ，空间 。