首页 > 代码库 > 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的项链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。