洛谷1823 [COI2007] Patrik 音乐会的等待

题意

有 $n(n\le 5\times 10^5)$ 个人，如果两个人之间所有人的身高都不高于他们，他们就可以互相看见。问有多少对人可以相互看见。

题解

总感觉之前做过但又找不到，所以还是写下来记录一下。

维护一个从大到小的单调栈，当前这个人 $i$ 可以和单调栈中所有 $h_j\le h_i$ 的人 $j$ 以及第一个比他高的人 相互看见。如果身高相同应该合并在一起。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=500005;
ll n,h[N],s[N],t,ans,cnt[N];

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++)
    {
        h[i]=read();
        cnt[i]=1;
        while (t && h[s[t]]<h[i]) ans+=cnt[s[t]],t--;
        if (t && h[s[t]]==h[i]) cnt[i]+=cnt[s[t]],ans+=cnt[s[t]],t--;
        if (t) ans++;
        s[++t]=i;
    }
    return !printf("%lld",ans);
}