区间众数是和分块脱不了干系的。
草怎么是权限题
题意简述
给出一个长为$n$的数列,$m$次询问一段区间内最小的区间众数,强制在线。
$1\leq l\leq r\leq40000,m\leq50000,1\leq a_i\leq 10^9$。
主要思路1
引理1
设$\operatorname{mode}(A)$为可重集合$A$的最小众数,则有$\operatorname{mode}(A\cup B)\in\operatorname{mode}(A)\cup B$。
引理1的证明
几乎是显然的。令$t=\operatorname{mode}(A\cup B)$,若$t$既不是$\operatorname{mode}(A)$,也不属于$B$,则$t$的出现次数就是在$A$中出现的次数。而这个次数应是不大于$\operatorname{mode}(A)$出现的次数的,出现矛盾。故引理1成立。
算法
离散化,分块,块大小$S$。
对于询问$[l,r]$,根据引理1,答案只可能是 $l,r$间所有完整块的最小众数 或 不完整块中出现的数。
对于一段完整块的最小众数$f[a][b]$,可以预处理,选定最左的块$a$后$O(n)$求出$f[a][i]$,其中$a\leq i$,总预处理复杂度$O(n\lfloor\frac{n}{S}\rfloor)$。
对于不完整的块,我们可以求出每种数在$[l,r]$中出现的次数。
怎么求出某种数在$[l,r]$中出现的次数?我们可以把每种数出现的位置按顺序丢到一个$\text{vector}$里,查找时找到第一个在$l$或其后出现的位置和最后一个在$r$或其前出现的位置即可,每次查询复杂度$O(\log_2cnt[a_i])=O(\log_2n)$。
所以每次询问区间$[l,r]$时间复杂度$O(Slog_2n)$。
平衡一下,块大小取$\sqrt{\frac{n}{\log_2n}}$,总复杂度$O(n\sqrt{n\log_2n})$($n,m$同阶)。
若本人推错了请指出
优化
有没有办法把这个$\sqrt{\log_2n}$去掉呢?
观察发现这个常数来自求某种数在$[l,r]$中出现的次数。
设$Sum(i,x)$表示$[1,i]$间$x$的个数,我们需要回答的就是$Sum(r,x)-Sum(l-1,x)$。
处理$C[b][x]$表示第$1$到第$b$块中$x$出现的次数,需要$O(n\lfloor\frac{n}{S}\rfloor)$的空间与时间。
处理$A[b][i][x]$表示从第$b$块开头开始的$i$个数中$x$的出现次数。因为每个块最多只有$S$种数,故复杂度$O(S^2\lfloor\frac{n}{S}\rfloor)=O(nS)$。
然后就可以$O(1)$地回答$Sum(i,x)$,可以将块大小设为$\sqrt{n}$,时空复杂度均为$O(n\sqrt{n})$($n,m$同阶)。
参考代码
然后你就会发现这玩意难写得很,所以我放弃了……
主要思路2
我们希望找到一个空间可以较小,且码量也较小的方法。
仍然离散化分块,块大小$S$,仍求出$f[a][b]$为一段完整块的最小众数,并附带求出该数的出现次数$num[a][b]$。
仍把每种数$x$的出现位置开一个$\text{vector}$(名$pos[x]$)按顺序存起来,同时对于数列中每个位置标记该位置在$\text{vector}$中的下标$id[i]$。
什么?没看懂?那就多看几遍
算法
设询问区间为$[l,r]$,包含完整块$[a,b]$。
首先$mode=f[a][b]$,出现次数$cnt=num[a][b]$。
然后处理两边的不完整块。
例如,对于$l$到块$a-1$的结尾处这部分:
假设处理到位置$i$,$a_i=x$。
那么,若$pos[x][id[i]+cnt]$仍存在且不在$r$的右边,显然可以更新$mode=x,cnt++$。
对于块$b+1$开头到$r$的这一部分,同理,只不过改成看$pos[x][id[i]-cnt]$是否不在$l$的左边。
可以发现,$cnt$最多更新$2S$次,若超过$2S$次则说明有数$x$在这段完整块$[a,b]$中出现次数大于$num[a][b]$,固然矛盾。所以每次询问时间复杂度$O(S)$。
预处理时间复杂度$O(n\lfloor\frac{n}{S}\rfloor)$,询问总时间复杂度$O(nS)$,故$S$取$\sqrt{n}$时复杂度降至最优$O(n\sqrt{n})$。
而空间复杂度,我们发现无论是$f,num$,还是$id,pos$,总共都只有$O(n)$的大小。
什么?没看懂?那就看看代码吧
参考代码
由于STL依赖症心血来潮,直接写了个$\text{pair}$……
1 |
|
扩展
[Ynoi2019模拟赛]Yuno loves sqrt technology III
这题是求区间众数的在区间中的出现次数。做法同上主要思路2(实际上$\text{lxl}$可能是国内第一个写这个思路的人?)。
注意卡常。
留下了卡不进总时间6.5s的泪水……
参考代码
1 |
|
参考
区间众数解题报告 - 陈立杰