题解
这题就是在教你怎么玩单调栈…
经典做法就是，维护一个不递增的栈，然后有人比栈顶的人还高的话，
就把他加进来，然后因为这个人肯定能看见他与他前面第一个比他高的人之间的人，
所以在出栈的时候累加答案。
同时还要注意人身高相等的情况。
下面我的程序给出的实现方式并不是一个很好的方式，所以有待改进
具体的改进方式应该就是令栈单调递减并且维护一段数据的大小…1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
typedef long long ll;
ll stack[500005],ans=0,tmp,len,lst;
int main(){
int i,top=1,n,j;
scanf("%d%lld",&n,&stack[0]);
for(i=1;i<n;i++){
scanf("%lld",&tmp);
while(top&&stack[top-1]<tmp)
top--,ans++;
stack[top++]=tmp;
if(top>1)ans++;
for(j=top-2;j&&stack[j]==tmp;j--,ans++);
}
printf("%lld\n",ans);
return 0;
}