Cow Frisbee (USACO Silver 2022 January)

不同高度的牛站成一排，问所有可以互相扔飞盘(中间的牛高度都小于两端的高度)的牛之间的距离总和。

直观感受一下：相邻牛可以；牛$i$右侧第一个高于$i$的牛$j$可以。从$j$再往右的牛都不行。中间的牛有一些可以，可能有一些不行。

那怎样找出中间所有可以的牛呢？两两测试是不行的，因为$N=3\cdot 10^5$。这时我们固定住右侧的$j$，所有和$j$可以配对的左侧牛，都呈现一个单调下降的序列。例子：

4 3 1 2 5 6 7

固定住5，我们看到可以与之配对的牛是4 3 2，是单调下降的。动态维护这样的具体单调性的数的列表，我们有一个标准的技巧，就是单调栈。

我们保证栈里元素是单调递减的，当看到一个新的$h[i]$的时候，栈顶所有比$h[i]$小的元素，再加上第一个比$h[i]$大的牛，都构成可互扔飞盘的牛，将所有比$h[i]$小的元素弹出来，留下比$h[i]$大的元素，再将$h[i]$压入栈，重复就可以了。

程序非常简单，重要的是通过这个题学会单调栈的技巧，以及看到类似结构时会使用。

📙 Cow Frisbee讲解幻灯片

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
ll ans;
int a[300005];
stack<int> s;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) {
            ans += i - s.top() + 1;
            s.pop();
        }
        if (!s.empty()) ans += i - s.top() + 1;
        s.push(i);
    }
    printf("%lld\n", ans);
    return 0;
}