P1972 [SDOI2009] HH的项链

本质上是区间查询 [ l , r ] [l,r] [l,r]不重复元素的个数. 考虑离线处理,按 r r r升序排序区间.假设当前区间为 [ l , r ] [l,r] [l,r],我们希望查询中的 q u e r y ( r ) − q u e r y ( l − 1 ) query(r)-query(l-1) query(r)−query(l−1)直接就是答案。考虑上一个查询的区间是 [ p r e l , p r e r ] [pre_l,pre_r] [prel​,prer​].区间 [ p r e r + 1 , r ] [pre_r+1,r] [prer​+1,r]是需要我们新插入的部分,如果我们能保证该区间插入不会破坏数据结构每个元素唯一性就成功了 考虑用树状数组维护这个东西,在 [ p r e r + 1 , r ] [pre_r+1,r] [prer​+1,r]插入时,使用一个 p o s [ i ] pos[i] pos[i]维护某个数字是否出现过,若出现过,当前最右边是多少. 因为我们回答查询的顺序是按 r r r升序的,所以对于两个重复元素的位置 i , j i,j i,j 如果 i < j iask[i].l>>ask[i].r; ask[i].id = i; } sort(ask.begin()+1,ask.end()); int pre_r = 1; for(int i=1;i