摘要

给定序列, 求有多少个区间满足 众数出现次数 \(>\lfloor (r-l+1)/2\rfloor\)

解

首先每个区间只会有一个数字.

关于数字 \(x\) 需要满足:

\[2(s_r-s_l)>r-l+1 \]

即

\[2s_r-r>2s_l-l \]

令 \(p_i=2s_i-i\), 则对于 \(x\), 其 \(p_i\) 是 \(\mathrm{cnt}(x)+1\) 段等差数列:

不难发现这样的等差数列共有 \(n\) 个. 注意到等差数列内部互相是不贡献的, 故我们对于每一个 \(x\) 顺序枚举每个段, 统计之前的贡献.

具体的, 令权值 \(i\in[-n,n]\) 个数为 \(a_i\), 实际实现需要偏移常量 \(wc=n+1\) 令 \(b_i=\sum a_i\). 对于单个权值 \(j\), 其之前贡献为 \(b_{j-1}\). 由于段推进, 这一段权值和为 \(\sum_{x-1}^{y-1} b_i\). 令 \(c_i=\sum b_i\), 则贡献就是 \(c_{y-1}-c_{x-2}\).

当推进完这个段后, 我们同时需要区间修改 \(a_i\). 故对 \(a_i\) 我们用差分维护, 及 \(a_i=\sum d_i\). 于是我们需要用树状数组维护三维前缀和.

\[\begin{equation} \begin{aligned} a&=1\\ &=2 \end{aligned} \end{equation}\]