自动搬运

查看原文

来自洛谷，原作者为

	V1mnkE **

搬运于2025-08-24 22:35:55，当前版本为作者最后更新于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;
}