4796099_ac_1094ms_4340k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int n;
int h[80005];
struct linkl
{
	linkl *next;
	__int64 ge;
	int h;
};
linkl * head;
int main()
{
	cin>>n;
	__int64 result=0;
	int i;
	for(i=0;i<n;i++) cin>>h[i];
	head=new linkl();
	head->h=h[n-1];
	head->ge=0;
	head->next=NULL;
	for(i=n-2;i>=0;i--)
	{
		__int64 temp=0;
		linkl *p=head;
		while(p)
		{
			if(h[i]>p->h) {temp+=p->ge+1;p=p->next;}
			else break;
		}
		linkl *q;
		q=new linkl();
		q->h=h[i];
		q->ge=temp;
		q->next=p;
		head=q;
		result+=temp;
	}
	printf("%I64d\n",result);
	return 0;
}