题目链接：镜中的昆虫
经典题了，我们首先回顾下颜色数的常见做法统计：
对每个位置维护一个 \(pre_i\)，表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。
查询 \([l,r]\) 得到颜色数，对于 \(pre_i<l\) 的 \(i\) 点，显然它就是这个区间内 \(a_i\) 对应颜色出现的第一个位置，我们把它作为贡献点，而其他的 \(pre_i \ge l\)，显然意味着，在当前区间内是存在前驱贡献点的，并不需要作为贡献点。所以颜色问题就转化为询问 \(i \in [l,r]\) 上有多少个 \(pre_i<l\)。
本题涉及到了区间覆盖，那么很显然，对于单纯地暴力修改每个 \(pre\) 是不现实的，这里先考虑不带修的区间段问题。
如果有若干段连续颜色段，询问某个段的颜色个数，那么一个考虑不带修，区别于传统的 \(HH的项链\) 问题解决方式，我们是预处理以后跑扫描线去做的，本质也是二维数点：我的某篇讲解文。参照了下题解区的一些大佬和我之前写的这篇文章，我对颜色数又有了新的看法。
对于一个极长连续颜色段，我们可以沿用之前文章中提到的代表元和作用范围的观点，对于一个极长颜色段来说，我们的当前点的作用范围为 \([pre[i],i]\)，代表元为 \(color_{first}\)。为什么选第一个点作为代表元贡献，那是因为，对于一个颜色段来说，它的贡献只有 \(1\)，而这个贡献可以选自这里面的任意一个元素，我们强制规定第一个点元素进行贡献，方便处理。
我们现在加上带修，看看上面的观点是否正确。对于如果上述的极长颜色连续段 \([l,r]\) 遇上了带修区间 \([L,R]\) 考虑有部分交集，并且二者颜色不同：
-
\(l<L,R\le r\)，这个时候会分为两段，显然前段 \([l,L-1]\) 依旧还是第一个颜色作为代表元，后半段则为 \([L,r]\)，\(L\) 作为新一段的代表元，显然是非常容易做到的。
-
在 \(1\) 的基础上，\(R<r\)，那么就是分为三段，最后两段为 \([L,R]\)，最后一段 \([R+1,r]\)，显然这三个极长连续段的第一个元素都可以分别作为代表元元素，且非常容易操作。
那么其实关于极长连续段我们就可以抽象为 \((pre[i],i)\) 的贡献，其中 \(i\) 为这个连续段的第一个元素，类似化段为点的思想，不得不说颜色数这个真是经典又永无止境的问题。
那么考虑正儿八经的带修，这玩意在线显然树套树空间好像不是很行，毕竟 \(64mb\) 限制，那么显然考虑离线，离线带修又有二维数点的，那么显然是 \(cdq分治\) 了。
现在考虑构造出修改与查询，查询很简单，对于区间查询，并且颜色数这个问题属于可差性问题，可以转化为前缀和作差：\([0,r]\) 上的颜色数减去 \([0,l-1]\) 上的颜色数。
考虑如何快速修改上述提到的极长连续颜色段，一个比较自然的想法就是分桶，为每个颜色进行分桶，那么我们可以快速知道待修改的颜色段。为了快速定位到 \([l,r]\) 的插入与删除，我们使用平衡树维护每个颜色桶。对于修改 \(pre\) 和传统颜色数问题一样，先去掉原有的 \(pre\) 贡献，再加入新的 \(pre\) 贡献。
-
对于某个颜色桶中增加一个 \([l,r]\)，我们可以快速基于二分出红色段，考虑 \(last\) 段的开头 \(l\) 修改 \(pre\) 为 \(l\)。而 \(l\) 处的 \(pre\) 应该修改该为蓝色段 \(pre\) 的 \(l\)。
-
对于删除，显然只需要考虑 \(last\) 的 \(pre\) 变为了蓝色段的 \(l\)。
当然蓝色段不存在的情况下自然是 \(0\) 了，特判一下。
对于一个 \([l,r]\) 上如何知道需要删除以及增加哪种颜色的连续段，这个玩意 \(ODT\) 就能办到，本题由于 \(ODT\) 只与修改的查询有关，修改只有区间赋值，所以复杂度也是完全正确的。非随机数据下的 \(ODT\) 这种颜色均摊为 \(O(n)\)，即最坏的时候就是 \([l,l]\) 的修改。
这里简单提提什么情况下 \(ODT\) 在非随机数据向下会被卡，首先除了区间覆盖操作以外，还有其他的操作，比如区间加操作，那么构造卡的数据很简单，比如区间 \(+\)，在初始状态下反复 \([1,n]\) 进行 \(+\)，每次修改即为 \(O(n)\)。另一种拥有区间查询询问，由于数据不随机，我们的 \([l,r]\) 可以每次 \([l,l]\) 使得颜色段数无法均摊到 \(\log{n}\)，这个时候查询每次 \([1,n]\)，那么查询的单次复杂度即为 \(O(n)\)，也能卡。本题仅仅用到总均摊数 \(O(n)\) 的结论，所以复杂度完全正确。假如是随机数据，则颜色段数量均摊为 \(O(\log{n})\)，注意前者为总均摊，这里说的随机数据为每时每刻均摊。其实也比较好理解，如果我的 \([l,r]\) 够长，那么其实跑出来就跟随机数据差不多了，够短只用到了遍历，最坏也仅仅是趋近于暴力，有根号分治那个思想的味道了。
那么这样一来就可以轻松地处理出修改和查询离线数据，我们的 \(cdq\) 本质是处理偏序问题的，注意到其实还有一个序：\(时间序\)，修改和查询的时间不能乱，这种序和数组下标序是差不多的，我们不需要刻意排序，直接按照对应的时间序下放就行。查询的时候，显然是 \(pre \le l-1\) 时，就加入 \(firstPos\) 这个点作为代表元贡献，其实可以看做就是一个带修版的 \(HH的项链\)，树状数组查询贡献，注意我们的每个查询要写两部分，写成前缀和作差的形式。在带修的基础上，加入了化段为点的思想，最后注意一些细节，比如离散化，初始化加入初始数组的 \((pre_i,i)\) 贡献。
最后注意到一个问题，对于一个区间覆盖，区间内的新的极长连续段怎么分配，其实对于同一颜色段，我们想怎么分配极长连续段都行，方便 \(ODT\) 的维护，这里给出一种巧妙的分割方式：\([l,r-1]\)，\([r,r]\)
标签：pre,颜色,题解,Ynoi2016,查询,P4690,修改,区间,极长 From： https://www.cnblogs.com/Athanasy/p/18042825