Min Max Subarrays

题目描述

注意：本题时限为 3s，为默认时限的 1.5 倍。 给定一个长度为 $N$ 的整数数组 $a_1,a_2,\dots,a_N$ （$2\le N\le 10^6, 1\le a_i\le N$）。请输出对数组 $a$ 的所有 $N(N+1)/2$ 个连续子数组，下面子问题答案之和。

给定一个非空整数列表，交替执行以下操作（从第一个操作开始），直到列表的大小恰好为 1。 将列表中两个相邻整数替换为它们的最小值。 将列表中两个相邻整数替换为它们的最大值。

求最终剩下的整数可能取得的最大值。

例如， [4, 10, 3] -> [4, 3] -> [4] [3, 4, 10] -> [3, 10] -> [10]

在第一个数组中，$(10, 3)$ 被替换为 $\min(10, 3)=3$，并且 $(4, 3)$ 被替换为 $\max(4, 3)=4$。

输入格式

第一行包含 $N$。 第二行包含 $a_1,a_2,\dots,a_N$。

输出格式

输出所有子数组对应子问题答案之和。

2
2 1

4

3
3 1 3

12

4
2 4 1 3

22

提示

$[2]$ 的答案是 $2$，$[1]$ 的答案是 $1$，并且 $[2, 1]$ 的答案是 $1$。 因此，我们的输出应为 $2+1+1 = 4$。

考虑子数组 $[2, 4, 1, 3]$。 对 (1, 3) 应用第一个操作后，新数组为 $[2, 4, 1]$。 对 (4, 1) 应用第二个操作后，新数组为 $[2, 4]$。 对 (2, 4) 应用第三个操作后，最终数字为 $2$。 可以证明 $2$ 是最终数字可能取得的最大值。

评分： 输入 4-5：$N\le 100$ 输入 6-7：$N\le 5000$ 输入 8-9：$\max(a)\le 10$ 输入 10-13：无额外限制。 题目鸣谢：Benjamin Qi

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum