题目
思路：用单调递增栈维护即可。
AC代码：
#include<stdio.h>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN = 80005;
const int INF = 0x3f3f3f3f;
int i, j, n, a[MAXN];
ll ans;
stack<int> s;
int main()
{
while(~scanf("%d", &n)) {
ans = 0;
while(!s.empty()) s.pop();//清空栈
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
//构建一个从栈顶到栈底递增的栈
a[n] = INF;//标记无穷大值，来计算最后栈中的递增序列的值
for(i = 0; i <= n; i++) {
while (!s.empty() && a[s.top()] <= a[i]) {//若栈不为空，且需要入栈的元素大于等于栈顶元素，破坏了栈的单调性，所以要将栈顶元素出栈
int tmp = s.top();
ans += (i - tmp - 1);//记录栈顶元素遇到第一个大于等于该元素的距离
s.pop();
}
s.push(i);//直到加入该元素，不会破坏栈的单调性，将该元素加入栈。
}
printf("%lld\n", ans);
}
return 0;
}
