题解 P7252 [JSOI2011] 棒棒糖

· · 题解

题意

经典题，区间严格过半众数。若不存在则输出 0。

sol

俺来介绍一些早已普及的高科技。

随机化一边去啦

一个非常规的巧妙做法

拆位，对于每一位组成的 01 序列，建前缀和以维护区间中 1（0 也可）的个数。

对于答案的每一位的状态，就是这一位对应的 01 序列的 [l,r] 区间中状态数较多的那个。

实现细节：拆位的时候，逐位分开处理，可以做到 O(n) 的空间复杂度。

做完了。。吗？

并没有！当区间中不存在严格众数时会出错。

所以我们需要一个 check 来验证求出来的答案是否正确。。换句话说就是求区间中某数出现次数。

莫队二次离线大家都学过吧？那你应该会那个离线扫描线

没学过也没有关系。我们将求 [l,r] 中 x 出现次数差分为 [1,r]-[1,l-1]。现在所有的询问都变成了 [1,k] 的形式。把所有询问按 k 归类（可以理解为排序，当然这一步是 O(n) 的）。

从小到大扫描。另外维护一个数组 t。设我们扫到了 p 这个位置则 t_i 所表示的就是 [1,p] 中 i 的出现次数。即每扫到一个位置 p，t_{a_p}\leftarrow t_{a_p}+1。

这样扫到 k 的时候，我们就可以 O(1) 回答所有“[1,k] 中 x 的出现次数”的询问！答案就是 t_x！太神奇了！

这个算法就完整了。可惜是离线的。下文会介绍另外一种 check 方法。

https://www.luogu.com.cn/paste/2jpfpq4j

O(n\log n)-(\log n)

正道

前置知识：摩尔投票法。

简介一下，考虑增量求出一个数组中的严格众数。维护当前严格众数 p 和一个 cnt。加入一个数 x 时，如果 cnt=0 就把 p 用 x 替换掉。再如果（注意“再”，是执行了上一步替换后再执行，保证了加入新的数后 cnt=1） x=p 就把 cnt 加 1，否则就减 1。

他是正确的因为即使严格众数和其他数都抵消了也不会影响。

应该可以看出他是一个半群信息。。通俗来讲就是一般线段树可以维护的东西。

所以你把他丢到线段树上就好了。（我用的 zkw）

同样要 check。

O(n)-(\log n)

https://www.luogu.com.cn/paste/9hoisbd3

真·高科技

嗯既然是半群信息，学术界有 O(n\alpha(n)) 的一般维护方式。\alpha 为反阿克曼函数。

但这个特殊问题有严格 O(n)-O(1) 的做法。

看这里 https://zhuanlan.zhihu.com/p/79423299 这里面有另外一种高论 check

sto hqztrue orz