[Ynoi2016] 镜中的昆虫——浅谈区间种类数问题

诈尸啦~
这篇博客是很久之前就想写的，总结一些关于区间种类数的问题，
正好一早上都在偏远机房上课，又不想写项目，就随便更新一点；

[Ynoi2016] 镜中的昆虫

题意：
给定一个长度为 $n$ 的序列，有 $m$ 次操作（$n,m<=1e5$)

• 操作一：将区间 $[l,r]$ 中的数改成 $x$
• 操作二：询问区间 $[l,r]$ 中的种类数

思路：
这个问题太复杂了，我们考虑简化问题：

1. 只有区间种类数。
   这是十分经典的问题；最典型的做法就是大家都知道的莫队做法，复杂度$O(n\sqrt{q})$的。
   这里给出另一种常见的做法：通过将询问离线，把询问挂到区间右端点上，再通过记录每个元素上一次出现的位置，扫一遍序列的同时，用树状数组维护每个左端点到当前右端点$r$的种类数（指针$r$是不断向右移动的），扫一遍序列的同时，遇到询问就在树状数组上查询即可，复杂度$O((n+q)log(n))$;
   哈，没想到吧，还有一种。用$pre[]$数组，表示上一个和当前元素相同的位置。那么想要求区间种类数，一个常见的套路是：区间中所有相同的元素，只有区间中最左边的位置做贡献。可以发现，这个位置 $i$ 满足 $pre[i]<l$ ，那么求区间种类数，就变成了求区间中有多少个位置，满足 $pre[i]<l$。如果将 $(i,pre[i])$看成二维平面上的一个点的话，那么问题就变成了求 $[l,r](0,l)$的矩形中有多少个点，天哪，多么经典的二维数点问题！（不会的同学，可以先去速通我的 $CDQ$题单）

2. 单点修改，询问区间种类数。
   可以发现，第一个问题中的第三个做法，可拓展性很强，考虑沿用这个做法。
   不难发现，进行一次单点修改时，只有三个位置的 $pre$值会发生变化，可以每个颜色开一个 $set$，那就知道是什么位置发生变化了，问题就变成了经典的带修二维数点问题。这边建议用 $CDQ$分治 实现，从修改对询问的影响入手，具体怎么实现，留给读者自行思考。

3. 区间赋值，询问区间种类数。
   先说结论：进行$m$次区间赋值，$pre[]$数组的变化是 $O(n+m)$的；
   对于同一个颜色的一整块，统一赋值成另一个颜色，对于 $pre$ 的变化也只有三个（因为原本同色，赋值之后还是同色的，$pre[i]=i-1$，不会发生变化）；
   那么这个问题中的颜色相同的一段 等于 上个问题中的一个点，从上面的证明我们知道，$pre$ 的改变次数 等于 删除的点的个数；已知，原本是$n$个点，一个赋值操作，最多能增加三个点（因为有可能把原本是一段的点，割开了），且每个点最多只能删除一次，那么 $pre$ 的变化次数就是 $O(n+m)$ 的，那么不就可以看成上一个问题，直接上 $CDQ$了吗！好耶！就是区间赋值会有点麻烦，上个珂朵莉加上每个颜色一个 $set$，就好多了~
   读者自己思考尝试一下吧。

代码：
无，
可能一段时间都不想写代码了…