A6121. 「USACO 2022 US Open Platinum」262144 Revisited
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目来自 [USACO 2022 US Open Contest, Platinum](http://usaco.org/index.php?page=open22results) Problem 1. [262144 Revisited](http://usaco.org/index.php?page=viewproblem2&cpid=1236)**
Bessie 喜欢在她的手机上下载游戏玩，尽管她确实发现对于她的大蹄子来说使用小触摸屏相当麻烦。
她对目前正在玩的游戏特别着迷。游戏从 $N$ 个 $1\ldots 10^6$ 范围内的正整数组成的序列 $a_1,a_2,\ldots,a_N$（$2\le N\le 262,144$）开始。在一次行动中，Bessie 可以取两个相邻的数字并将它们替换为一个大于两数最大值的数字（例如，她可以将相邻的一对数 $(5,7)$ 替换为 $8$）。游戏在 $N-1$ 次行动后结束，此时只剩下一个数字。游戏目标是*最小化*这个最终的数字。
Bessie 知道这个游戏对你来说太容易了。所以你的任务不仅仅是在 $a$ 上以最优方式玩游戏，而是在 $a$ 的每个连续子段上玩游戏。
输出 $a$ 的所有 $\frac{N(N+1)}{2}$ 个连续子段的最小最终数字之和。
Bessie 喜欢在她的手机上下载游戏玩，尽管她确实发现对于她的大蹄子来说使用小触摸屏相当麻烦。
她对目前正在玩的游戏特别着迷。游戏从 $N$ 个 $1\ldots 10^6$ 范围内的正整数组成的序列 $a_1,a_2,\ldots,a_N$（$2\le N\le 262,144$）开始。在一次行动中，Bessie 可以取两个相邻的数字并将它们替换为一个大于两数最大值的数字（例如，她可以将相邻的一对数 $(5,7)$ 替换为 $8$）。游戏在 $N-1$ 次行动后结束，此时只剩下一个数字。游戏目标是*最小化*这个最终的数字。
Bessie 知道这个游戏对你来说太容易了。所以你的任务不仅仅是在 $a$ 上以最优方式玩游戏，而是在 $a$ 的每个连续子段上玩游戏。
输出 $a$ 的所有 $\frac{N(N+1)}{2}$ 个连续子段的最小最终数字之和。
输入格式
输入的第一行包含 $N$。
第二行包含 $N$ 个空格分隔的整数，表示输入的序列。
第二行包含 $N$ 个空格分隔的整数，表示输入的序列。
输出格式
输出一行，包含所求的和。
输入输出样例
输入 #1
6 1 3 1 2 1 10
输出 #1
115
说明/提示
测试点 $ 2\sim 3 $ 满足 $N\le 300$。
测试点 $ 4\sim 5$ 满足 $N\le 3000$。
测试点 $ 6\sim 8$ 中，输入的序列中所有数的值不超过 $40$。
测试点 $ 9\sim 11$ 中，输入的序列是不下降的。
测试点 $ 12\sim 23 $ 没有额外限制。
测试点 $ 4\sim 5$ 满足 $N\le 3000$。
测试点 $ 6\sim 8$ 中，输入的序列中所有数的值不超过 $40$。
测试点 $ 9\sim 11$ 中，输入的序列是不下降的。
测试点 $ 12\sim 23 $ 没有额外限制。