首页 > 代码库 > bzoj1878[SDOI2009]HH的项链

bzoj1878[SDOI2009]HH的项链

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1878

//通过此题,我粗略地了解了什么是离线和它的好处

题意:有一串颜色,m条询问:l,r,目的是求第l个数到第r个数中有多少个不同的数。

解析:(这是江湖上流传的一种做法,觉得非常有道理QAQ)

         现将询问以l递增的顺序排列,设next[]为与当前颜色相同的下一位置,p[i]为第一个出现颜色i的位置,

         开始时,将所有颜色的最初点x pre[x]++

         从左往右扫,每扫到x就将pre[next[x]]++

         pre[]为前缀和,用树状数组维护

Q1:为什么要记录下一位置(next[])而不是上一位置?

A1:求完next[]后可生成每个颜色的最小位置,这与l递增的询问顺序相呼应。

Q2:更新pre[]时为什么只加不减?

A2:ans是前缀和相减得到,同时增减并不影响结果。

 

bzoj1878[SDOI2009]HH的项链