[SDOI2009] HH的项链

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

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

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


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

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

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

直接扫描线。

作者

nalemy

发布于

2023-10-18

更新于

2024-03-25

许可协议