BZOJ 3524 [Poi2014]Couriers

发布于 2017-05-24  162 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3524

题意:给一个长度为 n 的序列 a。1≤a[i]≤n。
          m 组询问,每次询问一个区间 [l,r],是否存在一个数在 [l,r] 中出现的次数大于 (r-l+1)/2。如果存在,输出这个数,否则输出 0。


原题干说的比较清楚,不复述了... 为了练习主席树用了主席树... 建树的过程和 K-th Number 是一样的,在查询时,我们考虑左右儿子的元素个数。由于大于 (r-l+1)/2 只可能在一边出现,所以直接判断一下然后找过去即可,若找不到,返回 0,详见代码

 


一个非常弱的准退役OIER