题解：P14558 [ROI 2013 Day2] 大规模预测

· · 题解

求长度为 n 序列 a 有多少个子区间的众数出现次数超过了区间长度的一半。n,a_i\le 5\times 10^5。

我们称在区间中出现次数超过区间长度一般的众数为绝对众数。显然，一个区间至多有一个绝对众数。因此枚举每种权值计算贡献。

记 S_{x,i} 表示 \sum\limits_{j=1}^i[a_j=x]。考虑一个区间 [l,r] 以 x 为绝对众数的充要条件，显然 S_{x,r}-S_{x,l-1}>\dfrac{r-l+1}{2}，整理得 2S_{x,r}-r>2S_{x,l-1}-(l-1)。我们记 w_{x,i}=2S_{x,i}-i，就是要统计满足 w_{x,r}>w_{x,l} 且 0\le l<r\le n 的 (l,r) 对数。将 w 的值域平移至从 1 开始。枚举 r，用数据结构维护 w 的值域前缀 [1,v) 的 l 个数 f_v，可以做到 \mathcal{O}\left(n^2\log n\right)。

考虑优化，记 x 出现的位置依次为 p_{x,1},\dots,p_{x,m}。同时不妨 p_{x,0}=0。我们发现对于 [p_{x,i},p_{x,i+1}) 内的 r，它们的 S_{x,r} 是相同的，因此 w_r 呈一段公差为 -1 的等差数列。考虑怎样快速计算每一段的贡献。考虑维护 f_v 表示这一段之前所有段的 w 前缀值域 [1,v) 中的 l 个数。

记这一段的等差数列为 w_r=k-r，那么这一段的贡献是：

\sum\limits_{j=p_{x,i}}^{p_{x,i+1}-1}f_{k-j}=\sum\limits_{j=k+1-p_{x,i+1}}^{k-p_{x,j}}f_j

相当于要查询 f 数组区间和。考虑每一段对 f 数组的影响是什么，记这一段等差数列的值域是 [L,R]。那么对于 [L,R] 内的 v，有 [L,v-1] 这些数可以对 f_v 产生贡献，为 v-L；对于 v\ge R+1，[L,R] 内的数都可以对 f_v 产生贡献。所以操作形如 f 数组区间加等差数列。用你喜欢的数据结构维护即可。

我使用了树状数组，考虑直接维护 f 数组的前缀和 F 数组，考虑每个操作对 F 产生怎样的影响，手推一下可以发现将 F_i 表示为关于 i 的二次函数，那么每次操作都相当于各次项系数区间加，查询是单点查，就可以树状数组维护了。

认为 n 和值域同阶，时间复杂度 \mathcal{O}(n\log n)，空间复杂度 \mathcal{O}(n)。