分析
单调找求右边第一个大于等于它的数,记录位置差值
上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> st;
long long n,a[100001],ans,t[100001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=1;i--)
{
while(!st.empty()&&a[st.top()]<a[i]) st.pop();
if(st.empty()) t[i]=n-i;
else t[i]=st.top()-i-1;
st.push(i);
}
for(int i=1;i<=n;i++)
{
ans+=t[i];
}
cout<<ans;
return 0;
}