在线严格 O(n)-O(1) 静态区间绝对众数

· · 算法·理论

给出一个长度为 n 的序列，q 次询问，每次求区间绝对众数，若不存在则任意输出。

前置知识：摩尔投票、四毛子、猫树。

不知道也无所谓，会提到。

很有意思的科技！我喜欢！

首先容易注意到的是绝对众数可以很容易的变成半群信息，具体方法就是摩尔投票。

考虑对于每个区间记两个信息 (w,v)，w 是该区间绝对众数的值，v 是该区间的摩尔值。

摩尔值由摩尔投票法给出。

枚举每一个区间内的数字，若 v=0 则将 v 加一并将 w 赋值为当前数字的值，否则若 w 等于该数字则将 v 加一，否则将 v 减一。

可以发现，两个区间的信息可以很容易合并。

(w_1,v_1)+(w_2,v_2)=\begin{cases}(w_1,v_1+v_2)&w_1=w_2\\(w_1,v_1-v_2)&v_1>v_2\\(w_2,v_2-v_1)&v_1\le v_2\end{cases}

然后那就简单了一点。

考虑将序列对 B_1 分块，对块内信息暴力枚举所有本质不同情况再枚举每个区间 O(B_1^{B_1+2})，块间考虑猫树维护，O(\frac{n}{B_1}\log n)。

取 B_1=\frac{\log n}{\log\log n} 得最优复杂度 O(n\log\log n)，并没有符合我们的要求。

那就再套一层 B_2 的块。

时间复杂度 O(\frac{n}{B_1}\log n+\frac{n}{B_2}\log B_1+B_2^{B_2+2})，取 B_1=\log n,B_2=\log\log n 即可得到最优复杂度 O(n)。

代码不想写。