题目分析

我们要求所有连续子数组的“最大可能最终值”之和。

对于每个子数组，操作规则：

1. 第一步：选择两个相邻数，用它们的最小值替换
2. 第二步：选择两个相邻数，用它们的最大值替换
3. 重复以上两步，直到剩下一个数
4. 目标：最大化最终剩下的数

---

核心思路

1. 关键观察

经过数学推导，可以证明：

• 当子数组长度 len 为奇数时，最终值等于最大值
• 当子数组长度 len 为偶数时，最终值等于最大值或次大值，取决于具体位置

更精确地：

• 对于长度为奇数的子数组，答案总是最大值
• 对于长度为偶数的子数组，答案可能是最大值或次大值，需要判断

---

2. 算法设计

2.1 长度 ≤ 6 的子数组

由于长度很小，可以直接暴力枚举所有可能的操作顺序（共 64 种情况），用二分法找到每个子数组的答案。

mp[len][mask] 数组预存了每个长度和二进制掩码对应的结果：

• len：子数组长度 (1-6)
• mask：二进制位表示哪些位置的数≥当前二分值
• 值为 1 表示该掩码对应的子数组最终能达到当前二分值

2.2 长度 ≥ 7 的子数组

使用分治算法：

• 将区间 [l, r] 分成两半 [l, mid] 和 [mid+1, r]
• 统计跨越中点的子数组的贡献
• 递归处理左右两半

对于跨越中点的子数组：

• 预处理每个位置向左/右的最大值和次大值
• 根据子数组长度的奇偶性和最大值位置计算贡献

---

3. 具体计算

3.1 奇偶性处理

Cnt(l, r, op) 函数计算区间 [l, r] 中与 op 奇偶性相同的位置个数：

• 用于统计满足特定奇偶性条件的子数组数量

3.2 分治中的四种情况

代码中分四种情况统计贡献：

1. 最大值在右半部分，长度为奇数
2. 最大值在左半部分，长度为奇数
3. 次大值在右半部分，长度为偶数
4. 次大值在左半部分，长度为偶数

每种情况都需要维护合适的指针，保证统计不重不漏。

---

4. 算法流程

1. 预处理小长度：对长度 1-6 的子数组暴力计算答案
2. 分治求解：对大长度子数组使用分治算法
3. 合并答案：将所有贡献累加到最终答案

---

5. 复杂度分析

• 小长度处理：O(6×N × log N) ≈ O(N log N)
• 分治算法：T(N) = 2T(N/2) + O(N) = O(N log N)
• 总复杂度：O(N log N)

对于 N ≤ 1e6 可接受。

---

6. 样例验证

样例 1

输入：2, [2,1]
处理：
- [2]：答案 2
- [1]：答案 1  
- [2,1]：答案 1
总和：4

样例 2

输入：3, [3,1,3]
处理：暴力+分治计算所有子数组答案
总和：12

---

7. 关键优化

7.1 预计算表

mp[len][mask] 预计算所有小长度情况的结果，避免重复计算。

7.2 分治技巧

通过维护最大值和次大值的前后缀，高效统计跨越中点的子数组贡献。

7.3 奇偶性分离

将奇数长度和偶数长度的子数组分开处理，简化逻辑。

---

算法标签

• 分治算法 (Divide and Conquer)
• 奇偶性分析 (Parity Analysis)
• 预计算 (Precomputation)
• 最大值次大值维护 (Max/Second Max Maintenance)

---

总结

本题通过分析操作的性质，发现答案只与子数组的最大值和次大值有关，且与长度的奇偶性密切相关。利用分治算法高效统计所有子数组的贡献，结合预计算处理小长度情况，在 O(N log N) 时间内解决问题。核心在于发现问题的数学本质，并用合适的数据结构优化统计过程。