「COI 2025」Bolivija 题解

核心思路

1. 问题转化

我们有一个长度为 $N$（奇数）的山脉序列 $v$，中心位置 $m = \frac{N+1}{2}$ 是最高峰。
选择两个参数 $A < B \leq v[m]$，照片包含所有高度在区间 $[A,B]$ 内的山体部分，且必须关于中心对称。

关键观察：对于照片对称，当且仅当对于每个对称位置对 $(i, N+1-i)$：

• 要么两个位置的山都在 $[A,B]$ 内
• 要么两个位置的山都不在 $[A,B]$ 内

2. 对称对分析

定义对称对 $(i, N+1-i)$，其中 $i = 1, 2, \ldots, \frac{N-1}{2}$。
对于每个对称对，设两座山的高度为 $a_i$ 和 $b_i$（假设 $a_i \leq b_i$）。

对于区间 $[A,B]$，该对称对破坏对称性的情况是：

• $A \leq a_i < B$ 且 $b_i < A$ 或 $b_i \geq B$（一个在区间内，一个在区间外）

3. 区间对 $(A,B)$ 的约束

实际上，$(A,B)$ 必须满足：对于每个对称对 $(a_i, b_i)$（其中 $a_i \leq b_i$）：

• 不能出现 $A \in [a_i+1, b_i]$ 且 $B \in [a_i+1, b_i]$ 的情况？
  让我们重新思考。

更准确地说，对于对称对 $(a_i, b_i)$：

• 如果 $A > b_i$：两座山都不在区间内 ✅
• 如果 $B \leq a_i$：两座山都不在区间内 ✅
• 如果 $A \leq a_i$ 且 $B > b_i$：两座山都在区间内 ✅
• 如果 $A \leq a_i$ 且 $a_i < B \leq b_i$：只有较矮山在区间内 ❌
• 如果 $a_i < A \leq b_i$ 且 $B > b_i$：只有较高山在区间内 ❌

因此，破坏对称性的情况是：

• $A \leq a_i$ 且 $a_i < B \leq b_i$
• $a_i < A \leq b_i$ 且 $B > b_i$

4. 平面点对计数

将 $(A,B)$ 看作二维平面上的点，其中 $0 \leq A < B \leq v[m]$。

每个对称对 $(a_i, b_i)$ 禁止了平面上的一个L形区域：

• 矩形 $[0, a_i] \times (a_i, b_i]$（左下角在 $(0,a_i+1)$，右上角在 $(a_i,b_i)$）
• 矩形 $(a_i, b_i] \times (b_i, v[m]]$

5. 容斥计数

初始所有点对数为 $\binom{v[m]+1}{2}$（因为 $A < B$，且 $0 \leq A,B \leq v[m]$）。

对于每个对称对，需要减去它禁止的区域面积。但多个对称对的禁止区域可能重叠，需要容斥。

更简单的方法：考虑每个 $B$ 值，计算可选的 $A$ 数量。

对于固定的 $B$，$A$ 必须满足：

• $A < B$
• 对于每个对称对 $(a_i, b_i)$：
  • 不能有 $A \leq a_i$ 且 $a_i < B \leq b_i$
  • 不能有 $a_i < A \leq b_i$ 且 $B > b_i$

这等价于：$A$ 必须 $\geq \max(\text{某些下界})$ 且 $\leq \min(\text{某些上界})$。

6. 高效算法

对于每个 $B$，定义：

• $L_B = \max\{a_i + 1 : a_i < B \leq b_i\}$（如果存在这样的对称对）
• $R_B = \min\{b_i : a_i < B \leq b_i\}$（如果存在这样的对称对）

那么对于给定的 $B$，可选的 $A$ 范围是：

• 如果存在 $a_i < B \leq b_i$，则 $A$ 必须 $\geq L_B$ 且 $A < \min(B, R_B+1)$
• 否则 $A$ 可以是 $0$ 到 $B-1$ 的任意值

7. 数据结构实现

使用 Fenwick 树或线段树维护：

• 每个对称对 $(a_i, b_i)$ 的影响
• 支持区间更新和查询

对于每个对称对，它在 $B$ 区间 $(a_i, b_i]$ 内产生约束：

• 要求 $A \geq a_i + 1$

因此，对于每个 $B$，$A$ 的最小值 $minA[B] = \max\{a_i + 1 : B > a_i \text{ 且 } B \leq b_i\}$

答案 = $\sum_{B=1}^{v[m]} \max(0, B - minA[B])$

8. 动态更新

当某个位置 $x$ 的高度改变时，影响对称对 $(x, N+1-x)$：

• 移除旧对称对的约束
• 添加新对称对的约束

使用数据结构维护所有对称对的 $(a_i, b_i)$，支持：

• 区间更新 $minA$ 数组
• 快速查询总和

算法实现

复杂度分析

• 预处理：$O(N \log N)$
• 每次更新：$O(\log N)$
• 总复杂度：$O((N+Q) \log N)$