题解
单调栈模板题。
从右到左记录一个递减的序列即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int st[80005][2],top=0,n,h[80005];
long long ans=0;
int main(){
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
scanf("%d",&h[i]);
st[top][0]=h[n-1],st[top++][1]=n-1;
for(i=n-2;i>=0;i--){
while(top&&h[i]>st[top-1][0])
top--;
if(!top)
ans+=(n-1-i);
else
ans+=(st[top-1][1]-i-1);
st[top][0]=h[i],st[top++][1]=i;
}
printf("%lld\n",ans);
return 0;
}