洛谷 P1972 [SDOI2009]HH的项链

洛谷 P1972 [SDOI2009]HH的项链 主席树+区间不同数字个数 😊 | Powered By HeartFireY

Problem Analysis

题目大意：给定 n n n个数的序列，以及随后的 m m m组询问。回答对于每组询问给出的 l , r l,r l,r，区间 [ l , r ] [l,r] [l,r]内不同数字的个数。

首先问题的形式与主席树是十分相似的：先给定序列，然后给定多组区间查询。但是显然不是单纯的维护区间第 k k k大的问题。

那么考虑如何将问题转化为主席树可维护的问题：我们对每个点维护一个数组元素 n x t [ i ] nxt[i] nxt[i]，表示最近的下一个同色点的下标。那么现在不难发现对于给定区间 [ l , r ] [l,r] [l,r]，如果 n x t [ i ] > r ,   i ∈ [ l , r ] nxt[i] > r,\ i \in [l,r] nxt[i]>r, i∈[l,r]，那么表示与 i i i相同颜色点位于区间之外。那么求不同颜色问题便转化为给定求所有满足 l < = i < = r ,   n x t [ i ] > r l> r; //cout