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

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

记 $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$，那么这一段的贡献是：

相当于要查询 $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)$。