序列数颜色trick

感觉很厉害

1. 判定颜色都是否出现过
   这一类可以采用特殊的处理方式达到单次 \(O(\log n)\)。
   考虑记录每个颜色的前驱位置 \(pre_i\)。
   那么对于 \([r+1,n]\) 的点，若存在 \(pre_i 则必然有颜色不在 \([l,r]\) 中出现。
   那么可以愉快地维护区间最小值，然后在线段树上二分。
   \(pre_i\) 可以用 multiset 维护。
   例题：P4632 [APIO2018] New Home 新家

2. 数区间颜色种数
   相当于计算 \([l,r]\) 中有多少个点满足 \(pre_i。
   那么相当于对 \((i,pre_i)\) 做二维数点。

3. 数单种颜色个数
   一般的经典动态开点线段树可以随便搞。
   颜色值域有限制时可以值域分块。