---

C. 子数组最小值求和 题解

---

一、题意理解

我们有一个数据结构，支持以下五种操作：

• pushback x：将值为 $x$ 的元素添加到末尾
• pushfront x：将值为 $x$ 的元素添加到开头
• popback：移除最后一个元素
• popfront：移除第一个元素
• min：将当前结构中的最小值累加到变量 $sum$ 上

目标：对任意给定的数组 $a$（长度为 $n$），构造一系列操作，使得最终 $sum$ 等于该数组所有非空子数组的最小值之和：

$$\sum_{0 \leq l \leq r < n} \min(a[l], \dots, a[r]) $$

操作总数不能超过 $n \cdot (n + 2)$。

---

二、核心思路

我们需要遍历所有子数组 $[l, r]$，并对每个子数组调用一次 min 操作。

直观想法：利用数据结构模拟滑动窗口。如果我们能按某种顺序，让结构恰好依次包含每个子数组的元素，并在每次变化后调用 min，就能累加所有子数组的最小值。

---

三、算法设计

3.1 基本策略

我们从数组的两端向中间逐层处理。设当前处理范围是 $[i, n-1-i]$（第 $i$ 层）。

第 $i$ 层（$i$ 从 $0$ 开始）：

• 如果 $i$ 是偶数（从左向右扫描）：

  • 依次将 $a[i], a[i+1], \dots, a[n-1]$ 从前端加入结构，每次加入后调用 min。
  • 这样可以得到所有以 $i$ 为左端点、以 $j$（$j \geq i$）为右端点的子数组最小值。
  • 扫描完后，从后端弹出一次（popback），移除最右侧元素。

• 如果 $i$ 是奇数（从右向左收尾）：

  • 此时结构中最右侧的元素是多余的，需要依次从前端弹出，并在每次弹出前调用 min。
  • 这样可以得到所有以 $j$（$j > i$）为左端点、以某个位置为右端点的子数组最小值。
  • 等价于将左边界向右收缩。

---

3.2 交替扫描过程详解

以 $n = 3$ 为例，数组 $a = [a[0], a[1], a[2]]$。

第 $0$ 层（$i = 0$，偶数，从左向右）：

操作	结构内容	min 对应子数组
pushfront a[0]	$[a[0]]$	—
min		$[0, 0]$
pushfront a[1]	$[a[1], a[0]]$	—
min		$[0, 1]$
pushfront a[2]	$[a[2], a[1], a[0]]$	—
min		$[0, 2]$
popback	$[a[2], a[1]]$	—

此时结构内容为 $[a[2], a[1]]$，对应子数组 $[1, 2]$。

第 $1$ 层（$i = 1$，奇数，从右向左收缩）：

操作	结构内容	min 对应子数组
min	$[a[2], a[1]]$	$[1, 2]$
popfront	$[a[2]]$	—
min		$[2, 2]$
popfront	$[]$	—

此时一共覆盖了所有子数组：$[0,0]$、$[0,1]$、$[0,2]$、$[1,2]$、$[2,2]$。

---

四、标程解析

标准程序 pashka 的实现非常简洁：

private fun solveTest() {
    val n = readInt()
    val res = emptyList<String>().toMutableList()
    for (i in 0..n - 1) {
        if (i % 2 == 0) {
            for (j in i..n - 1) {
                res.add("pushfront a[" + j + "]")
                res.add("min")
            }
            res.add("popback")
        } else {
            for (j in i..n - 1) {
                res.add("min")
                res.add("popfront")
            }
        }
    }
    println(res.size)
    for (s in res) {
        println(s)
    }
}

代码逻辑：

1. 外层循环 $i$ 从 $0$ 到 $n-1$，表示当前层的起始位置。

2. 当 $i$ 为偶数（从左向右扫描）：

   • 内层循环 $j$ 从 $i$ 到 $n-1$：
     • 执行 pushfront a[j]，将右侧元素逐个从前方压入；
     • 紧接着执行 min，记录当前结构对应的子数组最小值。
   • 循环结束后执行一次 popback，移除最右侧的元素，为下一层做准备。

3. 当 $i$ 为奇数（从右向左收缩）：

   • 内层循环 $j$ 从 $i$ 到 $n-1$：
     • 先执行 min，记录当前结构对应子数组的最小值；
     • 再执行 popfront，从前方移除元素，收缩左边界。

---

五、操作次数分析

每一层 $i$ 的操作次数：

• 偶数层：$(n - i)$ 次 pushfront + $(n - i)$ 次 min + $1$ 次 popback $= 2(n - i) + 1$
• 奇数层：$(n - i)$ 次 min + $(n - i)$ 次 popfront $= 2(n - i)$

总操作次数：

$$\begin{aligned} ops &= \sum_{i=0}^{n-1} \left[ 2(n-i) + (i \bmod 2 == 0\ ?\ 1 : 0) \right] \\[4pt] &= 2 \sum_{k=1}^{n} k + \lceil \frac{n}{2} \rceil \\[4pt] &= 2 \cdot \frac{n(n+1)}{2} + \lceil \frac{n}{2} \rceil \\[4pt] &= n(n+1) + \lceil \frac{n}{2} \rceil \end{aligned} $$

对于 $n \geq 1$，有：

$$n(n+1) + \lceil \frac{n}{2} \rceil \leq n(n+2)$$

因此操作数严格满足题目限制。

---

六、完整示例

样例 1：$n = 1$

3
pushback a[0]
min
popfront

过程：

• pushback a[0] → 结构：$[a[0]]$
• min → 累加 $\min(a[0])$，对应子数组 $[0,0]$
• popfront → 结构清空

覆盖子数组 $[0,0]$，输出总数 $3 \leq 1 \cdot (1+2) = 3$ ✅

---

样例 2：$n = 2$

6
pushfront a[1]
min
pushback a[0]
min
popfront
min

过程：

• pushfront a[1] → 结构：$[a[1]]$
• min → 子数组 $[1,1]$
• pushback a[0] → 结构：$[a[1], a[0]]$
• min → 子数组 $[1,0]$（即 $[0,1]$）
• popfront → 结构：$[a[0]]$
• min → 子数组 $[0,0]$

覆盖所有子数组 $[0,0]$、$[0,1]$、$[1,1]$，输出总数 $6 \leq 2 \cdot (2+2) = 8$ ✅

---

七、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<string> res;
    
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            // 偶数层：从左向右，将元素从前端加入
            for (int j = i; j < n; j++) {
                res.push_back("pushfront a[" + to_string(j) + "]");
                res.push_back("min");
            }
            res.push_back("popback");
        } else {
            // 奇数层：从右向左收缩，从前端弹出
            for (int j = i; j < n; j++) {
                res.push_back("min");
                res.push_back("popfront");
            }
        }
    }
    
    cout << res.size() << "\n";
    for (const string& s : res) {
        cout << s << "\n";
    }
    
    return 0;
}

---

八、复杂度分析

• 生成命令序列的时间复杂度为 $O(n^2)$，空间复杂度也为 $O(n^2)$。
• 对于 $n \leq 500$，操作数上限为 $500 \times 502 = 251000$，完全可行。
• 算法保证任意输入数组都能正确累加所有子数组的最小值。