CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目链接
维护一个递减的单调栈，每次插入后当前这只牛可以被q.size()-1只左边的高于他的牛看到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<deque>
using namespace std;
const int N=8e4+9;
typedef int ll;
typedef pair<int,ll> pil;
struct MonotoneQueue:deque<pil>
{
void push(pil p,int k)
{
while(!empty()&&back().second>=p.second)pop_back();
for(push_back(p); p.first-front().first>=k;)pop_front();
}
} q;
long long ans;
int n,h;
int main()
{
for(scanf("%d",&n); n--;)
scanf("%d",&h),q.push(pil(n,-h),N),ans+=q.size()-1;
printf("%lld",ans);
}