SPOJ DQUERY D-query(主席树)解题报告


解题思路

本题是要求区间内不同数的个数,这是主席树的常见应用之一了。

做法很简单,我们可以倒序(从右向左)建立主席树,如果一个值还没出现过,则直接插入,否则删除后再重新插入(相当于保留这个数最左出现的位置)。之后要查询 [l, r] 时,选用 l 位置的主席树,这时树中的数据是 [l, n] 范围内的,因此查询时需要传入 r 作为挡板,仅统计小于等于 r 的个数,这样就可以实现 [l, r] 区间不同数的查询。

当然也可以保留每个数最右出现的位置来正序建树,和上面的做法就反过来了。