P8094 [USACO22JAN] Cow Frisbee S 题解

V1mnkE · 2022-02-13 15:26:46 · 题解

思路

维护一个单调栈，每进入一个数 a_i，就向前扫描直到遇见一个 s_{top}>a_i，由于有 s_{top} 挡着，所以之后的我们全部都看不见，此时最终答案加上 (i-s_{top}+1)。

代码

#include <bits/stdc++.h>
using namespace std;
long long n,ans=0;
long long a[300005];
stack<long long>s;
int main() {
    cin>>n;
    for (int i=1;i<=n;i++)cin>>a[i];
    for (int i=1;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);
    }
    cout<<ans<<endl;
    return 0;
}