[SDOI2009] HH的项链

一种做法是，为等价类（颜色）寻找代表元，即待统计区间中最靠后者。

然后将询问按照右端点排序，保证统计区间为一个前缀。

如果区间中存在某种颜色，那么这种颜色的代表元一定在区间中，于是用树状数组维护当前前缀代表元数目，单点改、区间求和即可。

---

另一种做法：区间二维数点

对于数列中某个位置 $i$，记 $p_i$ 为 $i$ 之前最后一个颜色与 $i$ 相同的位置。

于是我们所求的，区间颜色数量，等价于求满足 $i\in[l,r],p_i<r$ 的位置数量。即代表元数量。

直接扫描线。