#PU1183. USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee

    ID: 1489 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan22来源:usaco.orgscoring:equal_test_cases单调栈二分答案

USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee

USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee

题目描述

Farmer John's NN cows (N≤3×105)N \leq 3 \times 10^5) have heights 1,2,…,N1, 2, \ldots, N. One day, the cows are standing in a line in some order playing frisbee; let h1…hNh_1 \ldots h_N denote the heights of the cows in this order (so the hh's are a permutation of 1…N1 \ldots N). Two cows at positions ii and jj in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than min⁡(hi,hj)\min(h_i, h_j). Please compute the sum of distances between all pairs of locations i<ji<j at which there resides a pair of cows that can successfully throw the frisbee back and forth. The distance between locations ii and jj is j−i+1j-i+1.

输入格式

The first line of input contains a single integer NN. The next line of input contains h1…hNh_1 \ldots h_N, separated by spaces.

输出格式

(见题面原文)

数据范围

Test cases 1-3 satisfy N≤5000N\le 5000. Test cases 4-11 satisfy no additional constraints. Problem credits: Quanquan Liu

样例

样例 1

7
4 3 1 2 5 6 7
24
The pairs of successful locations in this example are as follows:
(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)