P11585 [KTSC 2022 R1] 直方图
题目背景
**请使用 C++17 或 C++20 提交本题**
你需要在程序开头加入如下代码：
```cpp
#include
std::vector max_area(std::vector H);
```
题目译自 [2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2022/) T3「 [히스토그램](https://assets.ioikorea.kr/ioitst/2022/1/histogram/histogram_statement.pdf)」
题目描述
有一个由 $N$ 个底边平行于地面的矩形连续排列而成的直方图。每个矩形的宽度都是 $1$，并且从左到右第 $i (1 \leq i \leq N)$ 个矩形的高度为整数 $H_{i}$。
下图展示了一个可能的直方图示例。
在这个直方图中，我们希望找到不超过 $K$ 个矩形，这些矩形的底边平行于地面，且除了顶点和边之外的区域不重叠，并且每个边的长度都是整数，使得这些矩形的面积之和最大。这个值记为 $f(K)$。 请编写一个程序来计算 $f(1), f(2), f(3)$。
你需要实现以下函数：
`vector max_area(vector H);`
- 该函数只会被调用一次。
- 参数中给定的整数数组 $\texttt{H}$ 的大小为 $N$。数组的每个元素 $\texttt{H[i]} (0 \leq i \leq N-1)$ 表示从左到右第 $i+1$ 个矩形的高度 $H_{i+1}$。
- 该函数返回一个大小为 $1 \sim 3$ 的数组 $\texttt{A}$。$\texttt{A[i]} (0 \leq i
输入格式
示例评测程序按以下格式读取输入：
- 第 $1$ 行：$N$
- 第 $2$ 行：$H_{1}\,H_{2}\,\cdots H_{N}$
输出格式
示例评测程序按以下格式输出：
- 第 $1+i (0 \leq i
说明/提示
### 评分标准
假设 `max_area` 函数返回的数组为 $\texttt{A}$。
如果 $\texttt{A}$ 的大小不是 $1$ 到 $3$ 之间，则得 $0$ 分。
根据子任务的标准，如果 $f(1), \cdots, f(|\texttt{A}|)$ 中有任何一个值不正确，则得 $0$ 分。
如果 $f(1), \cdots, f(|\texttt{A}|)$ 的值都正确，则根据子任务的评分标准得分。
在上述标准中，$f(i)$ 正确意味着 $\texttt{A}$ 的大小至少为 $i$ 并且 $\texttt{A}[i-1]$ 的值等于 $f(i)$。
每个子任务的分数是子任务所有数据的最小分数。
### 样例解释 #1
考虑 $N=7, H=[3,2,1,2,1,4,3]$ 的情况。
评测程序将调用如下函数：
`max_area([3,2,1,2,1,4,3])=[7,11,13]`
下图展示了对于 $K=1,2,3$ 时面积之和最大的情况之一。
如果 `max_area` 函数返回 $[7, 11]$，则 $f(1)$ 和 $f(2)$ 都正确，可以根据子任务的评分标准得分。如果 `max_area` 函数返回 $[7, 12, 13]$，则尽管 $f(1)$ 和 $f(3)$ 正确，但 $f(2)$ 错误，因此得 $0$ 分。如果 `max_area` 函数返回 $[7, 11, 14]$，则尽管 $f(1)$ 和 $f(2)$ 正确，但 $f(3)$ 错误，因此得 $0$ 分。
这个样例满足子任务 $2,3,4,5$ 的条件。
### 样例解释 #2
考虑 $N=7, H=[1,2,3,4,5,6,7]$ 的情况。
评测程序将调用如下函数：
`max_area([1,2,3,4,5,6,7])=[16,21,24]`
这个样例满足所有子任务的条件。
### 样例解释 #3
考虑 $N=5, H=[1,3,4,3,1]$ 的情况。
评测程序将调用如下函数：
`max_area([1,3,4,3,1])=[9,11,12]`
这个样例满足子任务 $2,3,4,5$ 的条件。
### 数据范围
对于所有输入数据，满足：
- $1 \leq N \leq 5\cdot 10^5$
- $1 \leq H_{i} \leq 5\cdot 10^5 (1 \leq i \leq N)$
详细子任务附加限制及分值如下表所示。
|子任务|分值|约束|
| :----------: | :----------: | :----------: |
|$1$|$10$|$H_{i} \leq H_{i+1} (1 \leq i \leq N-1)$|
|$2$|$3$|$N \leq 500$|
|$3$|$15$|$N \leq 5000$|
|$4$|$27$|$N \leq 2\cdot 10^5$|
|$5$|$45$|无附加限制|