本文共 518 字，大约阅读时间需要 1 分钟。

Description

n个人排成一条直线（一排），给出队伍中每个人的身高，每个人只能看到站在他右边且个头比他小没有被其他人挡住（跟他身高相同也会挡出他）的人。请求出所有人可以看到的人数之和。

1<=N<=80,000

Sample Input

6
5
10
3
7
4
12
2

Sample Output

4

思路

一个单调栈就完了，单调栈里存右边比枚举到的人高或相等的下标。
code:

#include<iostream>#include<algorithm>#define ll long longusing namespace std;ll a[82001],n,ans,b[82001],r;int main(){    cin>>n; for (ll i=1;i<=n;i++) {     cin>>a[i]; } a[n+1]=0x3f3f3f3f; r=1; b[r]=n+1; for (ll i=n;i>0;i--) {     while (r&&a[b[r]]<a[i]) r--;  ans+=b[r]-i-1;//中间这一段都比i矮  b[++r]=i; } cout<<ans; return 0;}