「区间众数与中点」题解

问题分析

给定一个长度为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问区间 $[l,r]$ 内有多少个奇数长度的子区间 $[l',r']$ 满足：

1. 区间长度为奇数：$r'-l'+1$ 为奇数
2. 区间中点 $(l'+r')/2$ 是区间的众数

关键限制：

• 区间长度为奇数，所以中点位置 $mid = (l'+r')/2$ 是一个整数下标
• 要求 $a[mid]$ 是整个区间的众数
• 众数定义：出现次数最多的数（可以有多个众数，此时要求 $a[mid]$ 是其中之一）

核心观察

1. 中点的特殊性

对于奇数长度的区间 $[l',r']$，中点 $mid = (l'+r')/2$ 将区间分成两部分：

• 左半部分：$[l', mid-1]$，长度 $L = mid-l'$
• 右半部分：$[mid+1, r']$，长度 $R = r'-mid$

区间总长度：$L+R+1$ 为奇数，所以 $L+R$ 为偶数，$L$ 和 $R$ 奇偶性相同。

2. 中点成为众数的条件

设 $x = a[mid]$，区间中 $x$ 的出现次数为 $cnt_x$。

要使 $x$ 成为众数，需要满足：

• $x$ 的出现次数 $\geq$ 任何其他数 $y$ 的出现次数
• 即：对于所有 $y \neq x$，$cnt_x \geq cnt_y$

在 $[l',r']$ 中，$x$ 至少出现 1 次（在中点位置）。设左半部分 $x$ 出现 $L_x$ 次，右半部分出现 $R_x$ 次，则 $cnt_x = L_x + R_x + 1$。

对于其他数 $y$，设左半部分出现 $L_y$ 次，右半部分出现 $R_y$ 次，则 $cnt_y = L_y + R_y$。

条件变为：对于所有 $y \neq x$，

$$L_x + R_x + 1 \geq L_y + R_y$$

3. 简化条件

考虑所有数 $y \neq x$ 中最多的出现次数，设 $max_y = \max_{y \neq x} (L_y + R_y)$。

条件等价于：

$$L_x + R_x + 1 > max_y$$

或

$$L_x + R_x + 1 = max_y \text{ 且 } x \text{ 是众数之一（根据定义）} $$

实际上，由于众数可以有多个，$x$ 是众数当且仅当：

$$L_x + R_x + 1 \geq \max_{y \neq x} (L_y + R_y)$$

4. 转化为前缀和

设前缀和数组 $pre[i][v]$ 表示前 $i$ 个位置中值 $v$ 出现的次数。

则：

• $L_x = pre[mid-1][x] - pre[l'-1][x]$
• $R_x = pre[r'][x] - pre[mid][x]$
• $L_y = pre[mid-1][y] - pre[l'-1][y]$
• $R_y = pre[r'][y] - pre[mid][y]$

条件变为：

$$(pre[mid-1][x] - pre[l'-1][x]) + (pre[r'][x] - pre[mid][x]) + 1 \geq \max_{y \neq x} [(pre[mid-1][y] - pre[l'-1][y]) + (pre[r'][y] - pre[mid][y])] $$

简化：

$$pre[r'][x] - pre[l'-1][x] + 1 \geq \max_{y \neq x} [pre[r'][y] - pre[l'-1][y]] $$

即：

$$cnt_{[l',r']}(x) \geq \max_{y \neq x} cnt_{[l',r']}(y) $$

这恰好就是 $x$ 是区间 $[l',r']$ 众数的定义，所以推导是自洽的。

问题转化

我们需要计数满足条件的 $(l',r')$：

1. $l \leq l' \leq r' \leq r$
2. $r'-l'+1$ 为奇数
3. $a[mid]$ 是 $[l',r']$ 的众数，其中 $mid = (l'+r')/2$

关键洞察

对于固定的中点 $mid$，考虑所有以 $mid$ 为中点的奇数长度区间 $[l',r']$：

• $l' = mid - k$
• $r' = mid + k$
• 区间长度：$2k+1$，$k \geq 0$

条件变为：$a[mid]$ 是区间 $[mid-k, mid+k]$ 的众数。

算法思路

暴力方法（不可行）

对于每个询问 $[l,r]$，枚举所有可能的区间 $[l',r']$，检查条件。复杂度 $O(n^3)$ 或 $O(n^2)$，不可行。

优化思路

由于 $n \leq 5\times 10^5$，$m \leq 10^6$，需要接近 $O((n+m)\log n)$ 的算法。

观察1：对于固定中点 $mid$

对于每个位置 $mid$，我们可以预处理：最大的 $k$ 使得 $a[mid]$ 是 $[mid-k, mid+k]$ 的众数。

但一个更重要的观察：如果 $a[mid]$ 是 $[mid-k, mid+k]$ 的众数，那么它也是 $[mid-k', mid+k']$ 的众数对于所有 $k' < k$ 吗？不一定。

反例：考虑序列 [1,2,1]，中点位置2（值2）：

• $k=0$：区间[2,2]，2是众数
• $k=1$：区间[1,3]，2出现1次，1出现2次，2不是众数

所以性质不满足单调性。

观察2：众数出现的必要条件

设 $x = a[mid]$，区间 $[mid-k, mid+k]$ 中 $x$ 出现次数为 $cnt_x(k)$。

$x$ 是众数需要满足：$cnt_x(k) \geq cnt_y(k)$ 对于所有 $y \neq x$。

等价于：$cnt_x(k) \geq \lceil (2k+1)/2 \rceil = k+1$？不一定，众数不需要超过半数。

实际上，众数只需要出现次数最多，不一定过半数。

分块思想

由于 $n$ 和 $m$ 都很大，考虑使用莫队算法离线处理询问。

但是莫队算法处理的是区间查询，而我们需要计数子区间。可能需要二次离线莫队。

另一种思路：枚举中点

对于每个位置 $i$ 作为中点，考虑它能向右扩展多少。

设 $f(i)$ 表示以 $i$ 为中点，满足条件的最大区间半径 $k$。

然后对于询问 $[l,r]$，我们需要计数所有 $(i,k)$ 满足：

• $l \leq i-k \leq i+k \leq r$
• $k \leq f(i)$

这可以转化为二维数点问题。

计算 $f(i)$

对于每个中点 $i$，我们需要找到最大的 $k$ 使得 $a[i]$ 是 $[i-k, i+k]$ 的众数。

由于众数判断需要知道所有数的出现次数，直接计算 $f(i)$ 是困难的。

正解思路

关键洞察：出现次数差

定义 $diff(i,k) = cnt_{[i-k,i+k]}(a[i]) - \max_{y \neq a[i]} cnt_{[i-k,i+k]}(y)$

条件 $a[i]$ 是众数等价于 $diff(i,k) \geq 0$。

考虑随着 $k$ 增加，$diff(i,k)$ 的变化：

• 当 $k$ 增加1，区间扩展一个位置到左边 $i-k-1$ 和右边 $i+k+1$
• $cnt_{a[i]}$ 可能增加 0, 1 或 2
• 其他数的计数也可能增加

$diff(i,k)$ 不是单调的，但我们可以对每个 $i$ 二分查找最大的 $k$ 使得 $diff(i,k) \geq 0$。

高效计算 $diff(i,k)$

我们需要快速查询区间 $[i-k,i+k]$ 中：

1. $a[i]$ 的出现次数
2. 其他数的最大出现次数

可以使用可持久化线段树维护每个前缀的权值出现次数。

对于区间 $[L,R]$，$a[i]$ 的出现次数 = $query(R, a[i]) - query(L-1, a[i])$

其他数的最大出现次数 = 区间众数的出现次数（如果众数不是 $a[i]$）或次大出现次数（如果众数是 $a[i]$）。

这需要查询区间众数，可以使用摩尔投票法+线段树，但需要维护每个区间的候选众数和计数。

实际可行算法

由于 $n \leq 5\times 10^5$，我们可以对每个值 $v$ 单独处理。

对每个值 $v$ 的处理

考虑所有 $a[i] = v$ 的位置 $i$。对于每个这样的 $i$，我们想知道以 $i$ 为中点的区间 $[i-k,i+k]$ 中，$v$ 是否能成为众数。

在区间 $[i-k,i+k]$ 中，$v$ 出现次数 = 该区间内 $v$ 的位置数。

其他数的最大出现次数 ≤ 区间长度的一半？不一定。

实际上，我们可以对每个 $i$，找到最大的 $k$ 使得：

$$cnt_v([i-k,i+k]) > cnt_y([i-k,i+k]) \ \forall y \neq v $$

或者

$$cnt_v([i-k,i+k]) \geq cnt_y([i-k,i+k]) \ \forall y \neq v $$

且 $v$ 是众数之一。

转换为连续段问题

对于固定的 $v$，考虑所有 $a[i]=v$ 的位置。对于每个这样的 $i$，向左右扩展，直到遇到某个位置使得其他数的出现次数超过 $v$。

设 $left[i]$ 表示向左最多能扩展到什么位置，$right[i]$ 表示向右最多能扩展到什么位置，使得 $v$ 是以 $i$ 为中点的区间的众数。

最终算法框架

预处理阶段

1. 对序列分块，块大小 $B = \sqrt{n}$ 或 $B = 1000$
2. 预处理每个块内每个值的出现次数前缀和
3. 对于每个位置 $i$，预处理以 $i$ 为中点的最大半径 $R[i]$，使得 $a[i]$ 是众数
   • 使用双指针扩展，利用分块信息快速计算区间内各值出现次数
   • 复杂度 $O(n \cdot B)$ 或 $O(n \sqrt{n})$

查询阶段

对于询问 $[l,r]$：

1. 计算所有完全在 $[l,r]$ 内的区间 $[i-k,i+k]$ 满足 $k \leq R[i]$
2. 这可以转化为：对于每个 $i \in [l,r]$，满足条件的 $k$ 数量为 $\min(R[i], \min(i-l, r-i)) + 1$
   • 因为 $k$ 需要满足 $i-k \geq l$ 且 $i+k \leq r$

所以答案 = $\sum_{i=l}^r [\min(R[i], \min(i-l, r-i)) + 1]$

但是这样会重复计算 $k=0$ 的情况（长度为1的区间），题目中长度为1的区间自然满足条件（唯一的元素是众数）。

优化查询

我们需要快速计算 $\sum_{i=l}^r \min(R[i], \min(i-l, r-i))$

将区间分成三部分：

1. 左半部分：$i$ 靠近 $l$，限制是 $i-l$
2. 中间部分：$i$ 不受边界限制，限制是 $R[i]$
3. 右半部分：$i$ 靠近 $r$，限制是 $r-i$

具体地：

• 对于 $i \in [l, l+\min(R[i])]$，限制是 $i-l$
• 对于 $i \in [r-\min(R[i]), r]$，限制是 $r-i$
• 对于中间的 $i$，限制是 $R[i]$

但是 $\min(R[i])$ 不是常数，所以需要更精细的处理。

实际实现策略

由于 $m$ 很大，需要 $O(1)$ 或 $O(\log n)$ 的查询。

可以考虑预处理前缀和数组：

• $S1[i] = \sum_{j=1}^i R[j]$
• $S2[i] = \sum_{j=1}^i j$（等差数列和）
• $S3[i] = \sum_{j=1}^i [R[j] \geq \text{某个值}]$

然后对于询问 $[l,r]$，可以 $O(1)$ 计算：

$$\sum_{i=l}^r \min(R[i], \min(i-l, r-i))$$

通过分类讨论 $i$ 的位置。

复杂度分析

预处理

• 计算 $R[i]$：$O(n \sqrt{n})$ 或 $O(n \log n)$
• 预处理前缀和：$O(n)$

查询

• 每个询问 $O(1)$ 或 $O(\log n)$
• 总复杂度：$O(m)$ 或 $O(m \log n)$

总结

本题是一个复杂的数据结构+组合计数问题：

1. 将问题转化为对每个中点求最大扩展半径
2. 使用分块+双指针预处理 $R[i]$
3. 将询问转化为前缀和计算
4. 通过分类讨论实现快速查询