题目大意

给定长度为 $N$ 的投票序列，统计所有子区间中，存在某个候选人得票数超过区间长度一半的区间数量。

解题思路

核心思想

基于候选人的贡献计算 + 差分数组优化

1. 分别考虑每个候选人：对于每个候选人 $i$，计算有多少区间中该候选人是绝对众数
2. 坐标变换技巧：将问题转化为前缀和的形式
3. 差分数组优化：使用差分数组高效统计满足条件的区间

算法流程详解

1. 问题转化

对于候选人 $i$，考虑区间 $[l, r]$，该候选人是绝对众数的条件是：

等价于：

2. 关键观察

定义 $f(j) = 2 \times count_i(1, j) - j$，其中 $count_i(1, j)$ 是前 $j$ 个位置中候选人 $i$ 出现的次数。

那么对于区间 $[l, r]$，候选人 $i$ 是绝对众数当且仅当：

3. 算法步骤

对于每个候选人 $i$：

1. 预处理位置：记录候选人 $i$ 出现的所有位置
2. 坐标变换：通过线性变换将问题转化为统计满足 $f(r) > f(l-1)$ 的区间
3. 差分统计：使用差分数组高效计算满足条件的区间数量
4. 累加贡献：将每个候选人的贡献相加得到最终答案

4. 复杂度分析

• 时间复杂度：$O(N + K)$

  • 每个位置最多被处理常数次
  • 使用差分数组使得统计操作高效

• 空间复杂度：$O(N + K)$

总结

本题的巧妙解法在于：

1. 分离贡献思想：将问题分解为每个候选人的独立贡献，避免复杂的状态转移

2. 数学变换技巧：通过巧妙的坐标变换，将绝对众数条件转化为简单的不等式

3. 差分数组优化：使用差分技术高效统计满足条件的区间数量，避免暴力枚举

4. 线性复杂度：算法在 $O(N + K)$ 时间内解决问题，适用于大规模数据