Cow Frisbee

题目描述

农夫约翰有 $N$ 头奶牛（$N \leq 3 \times 10^5$），它们的身高分别为 $1, 2, \ldots, N$。 有一天，奶牛们按某种顺序站成一排玩飞盘；设 $h_1 \ldots h_N$ 表示奶牛在这一顺序下的身高（因此这些 $h$ 构成 $1 \ldots N$ 的一个排列）。

位于队列中位置 $i$ 与 $j$ 的两头奶牛，能够成功来回投掷飞盘，当且仅当它们之间的每一头奶牛的身高都小于 $\min(h_i, h_j)$。

请计算所有满足 $i<j$ 且对应位置上的奶牛能够成功来回投掷飞盘的地点对 $(i,j)$ 的距离之和。位置 $i$ 与 $j$ 的距离定义为 $j-i+1$。

输入格式

第一行输入一个整数 $N$。第二行输入 $h_1 \ldots h_N$，用空格分隔。

输出格式

输出所有能够成功来回投掷飞盘的地点对的距离之和。注意：本题中涉及的整数可能非常大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

7
4 3 1 2 5 6 7

24

提示

本例中成功的位置对如下： (1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

评分 测试点 1-3 满足 $N\le 5000$。 测试点 4-11 没有额外限制。

题目来源：Quanquan Liu

标签: USACO|2022|Silver

来源

USACO|2022|Silver