5696：区间的价值

题目描述

我们定义“区间的价值”为一段区间的最大值*最小值。

一个区间左端点在$L$，右端点在$R$，那么该区间的长度为$(R-L+1)$。

现在聪明的杰西想要知道，对于长度为$k$的区间，最大价值的区间价值是多少。

当然，由于这个问题过于简单。

我们肯定得加强一下。

我们想要知道的是，对于长度为$1\sim n$的区间，最大价值的区间价值分别是多少。

样例解释：

长度为$1$的最优区间为$2-2$ 答案为$6*6$

长度为$2$的最优区间为$4-5$ 答案为$4*4$

长度为$3$的最优区间为$2-4$ 答案为$2*6$

长度为$4$的最优区间为$2-5$ 答案为$2*6$

长度为5的最优区间为$1-5$ 答案为$1*6$

输入解释

多组测试数据

第一行一个数$n(1\leq n\leq 100000)$。

第二行$n$个正整数$(1\leq a_{i}\leq 10^{9})$，下标从$1$开始。

由于某种不可抗力，$a_{i}$的值将会是$1\sim 10^{9}$内<b style="color:red;">随机产生</b>的一个数。（除了样例）

输出解释

输出共$n$行，第$i$行表示区间长度为$i$的区间中最大的区间价值。

输入样例

5
1 6 2 4 4

输出样例

来自杭电HDUOJ的附加信息

Recommend

wange2014

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2016"百度之星" - 初赛（Astar Round2B）

源链接： HDU-5696

最后修改于 2020-10-25T23:24:53+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
10000/5000MS(Java/Others)	65536/65536K(Java/Others)