更新题目交换一次：下标加权和最大

题目 visa-swap-max-index-weighted-sum · 修改（rev 5） · cc · 2026-10-27 00:33
body

@@ -55,17 +55,17 @@
 ```
 
-所以要找左边大、右边小、离得远的一对。直接枚举所有 `i < j` 是 O(n²)。
+所以要找左边大、右边小、离得远的一对。直接枚举所有 `i < j` 是 $O(n^2)$。
 
 可以先排除一些位置。左端点 `i` 前面如果有位置 `i'` 满足 `a[i'] >= a[i]`，那么对任何收益为正的 `j`，两个因子 `a[i'] - a[j] >= a[i] - a[j] > 0`、`j - i' > j - i` 都不变小，换成 `i'` 收益不会变小。所以左端点只需要考虑**严格前缀最大值**的位置（比前面所有数都大的位置）。同理，右端点只需要考虑**严格后缀最小值**的位置（比后面所有数都小的位置）。收益不为正的对本来就不会被选上，因为答案的起点是「不交换」，收益 0。
 
-随机数据上两张候选表都很短（元素互不相同时，前缀最大值个数的期望约为 ln n），但最坏仍是 O(n²)，见「复杂度」。
+随机数据上两张候选表都很短（元素互不相同时，前缀最大值个数的期望约为 $\ln n$），但最坏仍是 $O(n^2)$，见「复杂度」。
 
 > [!say] Swapping positions i and j changes the sum by (a[i] minus a[j]) times (j minus i). A left endpoint only matters if it is larger than everything before it, and a right endpoint only matters if it is smaller than everything after it, so I only pair those candidates.
 
-> [!optional] n 到 10^5 而且数据刻意构造时，可以用分治把候选对的枚举降到 O(n log n)。记收益为 `w(i, j) = (a[i] - a[j]) · (j - i)`，左候选按下标取 `i1 < i2`，右候选取 `j1 < j2`。展开后 `a[i]·i`、`a[j]·j` 两类项相消，得到 `w(i1,j1) + w(i2,j2) - w(i1,j2) - w(i2,j1) = (a[i2]-a[i1])·(j2-j1) + (a[j2]-a[j1])·(i2-i1)`。两张候选表的值都随下标严格递增，所以右边严格大于 0。
+> [!optional] n 到 $10^5$ 而且数据刻意构造时，可以用分治把候选对的枚举降到 $O(n \log n)$。记收益为 `w(i, j) = (a[i] - a[j]) · (j - i)`，左候选按下标取 `i1 < i2`，右候选取 `j1 < j2`。展开后 `a[i]·i`、`a[j]·j` 两类项相消，得到 `w(i1,j1) + w(i2,j2) - w(i1,j2) - w(i2,j1) = (a[i2]-a[i1])·(j2-j1) + (a[j2]-a[j1])·(i2-i1)`。两张候选表的值都随下标严格递增，所以右边严格大于 0。
 >
 > 由此推出：左端点往右移，最优右端点不会往左移。设 `j*` 是 `i1` 的一个最优右端点，`j < j*`。`i1` 的最优性给出 `w(i1,j*) - w(i1,j) >= 0`，上式（取 `j1 = j`、`j2 = j*`）给出 `w(i2,j*) - w(i2,j) > w(i1,j*) - w(i1,j)`，所以 `w(i2,j*) > w(i2,j)`，`j` 不可能是 `i2` 的最优右端点。
 >
-> 上面的推导没管 `j > i` 的限制，这不影响结果：右候选 `j` 在 `i` 左边时，`a[j]` 不大于它后面的 `a[i]`，而 `j - i < 0`，按公式算出的收益不为正，超不过「不交换」的 0。所以分治时不用管这条限制：对中间那个左候选扫一遍全部右候选，找到最优位置 `k`，左半边的左候选只在 `k` 及其左边找，右半边只在 `k` 及其右边找。每层递归扫的总长度是 O(n)，共 O(log n) 层。
+> 上面的推导没管 `j > i` 的限制，这不影响结果：右候选 `j` 在 `i` 左边时，`a[j]` 不大于它后面的 `a[i]`，而 `j - i < 0`，按公式算出的收益不为正，超不过「不交换」的 0。所以分治时不用管这条限制：对中间那个左候选扫一遍全部右候选，找到最优位置 `k`，左半边的左候选只在 `k` 及其左边找，右半边只在 `k` 及其右边找。每层递归扫的总长度是 $O(n)$，共 $O(\log n)$ 层。
 
 ## 代码
@@ -129,11 +129,11 @@
 | `[3, 2, 1]` | 读法二的错误做法：把所有正收益相邻对都加上 | 错误做法 12，DP 11，暴力枚举 11 |
 | `[5, 1, 4, 0]` | 读法三的错误做法：只看相邻对 | 错误做法 23，候选对枚举 34（交换 5 和 0），暴力枚举 34 |
-| `[]`、`[7]`、`[1, 2, 3]`、`[-3, -1, -2]`、`[10^9, -10^9]` | 空数组、单元素、已经最优、负数、极值 | 两个函数都和暴力枚举一致，分别是 0、7、14、-10、10^9 |
+| `[]`、`[7]`、`[1, 2, 3]`、`[-3, -1, -2]`、`[10^9, -10^9]` | 空数组、单元素、已经最优、负数、极值 | 两个函数都和暴力枚举一致，分别是 0、7、14、-10、$10^9$ |
 | 5000 组随机数组，长度 0 到 10，值在 -10 到 10 | 对拍 | 读法二、读法三都和暴力枚举 0 处不一致 |
 
 ## 复杂度
 
-- 读法二：O(n) 时间，O(1) 额外空间。
-- 读法三：建两张候选表 O(n)，额外空间 O(n)。枚举候选对最坏 O(n²)：比如 `[6, 7, 8, 9, 1, 2, 3, 4]` 这样两段递增拼起来，前半段全是左候选，后半段全是右候选，n/2 × n/2 对的收益都为正。要压到 O(n log n) 见思路第 2 节的可选知识框。
+- 读法二：$O(n)$ 时间，$O(1)$ 额外空间。
+- 读法三：建两张候选表 $O(n)$，额外空间 $O(n)$。枚举候选对最坏 $O(n^2)$：比如 `[6, 7, 8, 9, 1, 2, 3, 4]` 这样两段递增拼起来，前半段全是左候选，后半段全是右候选，$n/2 \times n/2$ 对的收益都为正。要压到 $O(n \log n)$ 见思路第 2 节的可选知识框。
 
 ## 易错点
更新题目 交换一次：下标加权和最大

body

meta

更新题目交换一次：下标加权和最大
