最小最大子数组

 1 Sec 256 MB |  Markdown 获取标签

 

题目描述

给定长度为 nn 的整数数组 a1,a2,,aN(2N106,1aiN)a_1,a_2,\cdots,a_N(2\leq N \leq 10^6,1\leq a_i \leq N).

请输出所有 N(N+1)/2N*(N+1)/2aa 的连续子数组的以下子问题答案之和.

子问题

给定一个非空序列,交替执行以下操作(从第一个操作开始),直到列表大小恰为一.

  1. 将列表内的两个相邻整数替换为它们的较小值。
  2. 将列表内的两个相邻整数替换为它们的较大值。

求最终余下的整数的最大可能值.

输入格式

第一行包含一个整数 NN.

第二行包含 a1,a2,,ana_1,a_2,\cdots,a_n.

输出格式

一个整数表示答案.

样例输入 #1

2
2 1

样例输出 #1

4

样例输入 #2

3
3 1 3

样例输出 #2

12

 

 您尚未登录,无法进行代码提交

2025 春季 组队排位赛(一)

2025-03-09 12:05
2025-03-09 17:05
Ended