#PU1500. USACO 2025 February Contest, Platinum — Problem 1. Min Max Subarrays

USACO 2025 February Contest, Platinum — Problem 1. Min Max Subarrays

USACO 2025 February Contest, Platinum — Problem 1. Min Max Subarrays

题目描述

Note: The time limit for this problem is 3s, 1.5x the default. You are given a length-NN integer array a1,a2,…,aNa_1,a_2,\dots,a_N (2≤N≤106,1≤ai≤N2\le N\le 10^6, 1\le a_i\le N). Output the sum of the answers for the subproblem below over all N(N+1)/2N(N+1)/2 contiguous subarrays of aa. Given a nonempty list of integers, alternate the following operations (starting with the first operation) until the list has size exactly one. Replace two consecutive integers in the list with their minimum. Replace two consecutive integers in the list with their maximum. Determine the maximum possible value of the final remaining integer. For example, [4, 10, 3] -> [4, 3] -> [4] [3, 4, 10] -> [3, 10] -> [10] In the first array, (10,3)(10, 3) is replaced by min⁡(10,3)=3\min(10, 3)=3 and (4,3)(4, 3) is replaced by max⁡(4,3)=4\max(4, 3)=4.

输入格式

The first line contains NN. The second line contains a1,a2,…,aNa_1,a_2,\dots,a_N.

输出格式

The sum of the answer to the subproblem over all subarrays.

数据范围

Inputs 4-5: N≤100N\le 100 Inputs 6-7: N≤5000N\le 5000 Inputs 8-9: max⁡(a)≤10\max(a)\le 10 Inputs 10-13: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

2
2 1
4
The answer for $[2]$ is $2$, the answer for $[1]$ is $1$, and the answer for
$[2, 1]$ is $1$.
Thus, our output should be $2+1+1 = 4$.

样例 2

3
3 1 3
12

样例 3

4
2 4 1 3
22
Consider the subarray $[2, 4, 1, 3]$.
Applying the first operation on (1, 3), our new array is $[2, 4, 1]$.
Applying the second operation on (4, 1), our new array is $[2, 4]$.
Applying the third operation on (2, 4), our final number is $2$.
It can be proven that $2$ is the maximum possible value of the final number.