题目：P8094 [USACO22JAN] Cow Frisbee S

题目描述

Farmer John 的 $N(N\le 3\times 10^5)$ 头奶牛的高度为 $1,2,\dots ,N$。一天，奶牛以某个顺序排成一行玩飞盘；令 $h_1\dots h_N$ 表示此顺序下奶牛们的高度（因此 $h$ 是 $1\dots N$ 的一个排列）。

队伍中位于位置 $i$ 和 $j$ 的两头奶牛可以成功地来回扔飞盘当且仅当她们之间的每头奶牛的高度都低于 $\min (h_i,h_j)$。

请计算所有可以成功地来回扔飞盘的奶牛所在的位置对 $i\le j$ 之间的距离总和。位置 $i$ 和 $j$ 之间的距离为 $j-i+1$。

输入格式

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

输出格式

输出可以成功地来回扔飞盘的奶牛所在的位置对 $i\le j$ 之间的距离总和。注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C 或 C++ 中的 “long long”）。

输入输出样例 #1

输入 #1

7
4 3 1 2 5 6 7

输出 #1

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 没有额外限制。

代码

#include<iostream>using namespace std;typedef long long LL;
const int MaxN = 3e5 + 10;int N, st[MaxN], tt, h[MaxN];
LL res = 0;void insert(int x){st[++ tt] = x;
}void dele(){tt --;
}bool isempty(){return tt <= 0;
}int main(){cin >> N;for(int i = 1; i <= N; i ++){cin >> h[i];}for(int i = 1; i <= N; i ++){while(!isempty() && h[i] > h[st[tt]]){res += i - st[tt] + 1;dele();}if(!isempty()){res += i - st[tt] + 1;}insert(i);}cout << res;return 0;
}

结果