记录编号	329089	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	3.192 s
提交时间	2016-10-24 20:40:45	内存使用	23.59 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn=100000+10;
int n;int ans=0;
int ma[maxn][30];
int mi[maxn][30];
int h[maxn];
// ps:zuo da zhi zuo kao zui xiao zhi you kao
void st()
{
	for(int j=1;j<30;j++)
		for(int i=1;i<=n;i++)
			{
				if((1<<j)+i-1<=n)
				{
					//ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
					if(h[ma[i][j-1]]>=h[ma[i+(1<<(j-1))][j-1]])
					ma[i][j]=ma[i][j-1]; else ma[i][j]=ma[i+(1<<(j-1))][j-1];
					//mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
					if(h[mi[i][j-1]]<h[mi[i+(1<<(j-1))][j-1]])
					mi[i][j]=mi[i][j-1]; else mi[i][j]=mi[i+(1<<(j-1))][j-1];
	
				}
			}
}
int maxsum(int l,int r)
{
	int len=(r-l)+1;
	int j=log(len)/log(2.0); //printf("%d",j);
	//return max(ma[l][j],ma[r-(1<<j)+1][j]);
	int a=ma[l][j]; int b=ma[r-(1<<j)+1][j];
	if(h[a]>=h[b]) return a;
	else return b;
}
int minsum(int l,int r)
{
	int len=(r-l)+1;
	int j=log(len)/log(2.0);
	//return min(mi[l][j],mi[r-(1<<j)+1][j]);
	int a=mi[l][j];int b=mi[r-(1<<j)+1][j];
	if(h[a]<h[b]) return a; else return b;
}
void dfs(int l,int r)
{	
	
	//printf("%d  %d",l,r);
	if(l>=r) return;
	/*if(l==r) 
	{
		ans=max(ans,1); 
		return;
	}*/
	int maxpos=maxsum(l,r);
	int minpos=minsum(l,r);
	if(maxpos>minpos)
	{
		ans=max(ans,maxpos-minpos+1);
		dfs(l,minpos-1);
		dfs(maxpos+1,r); return ;
	}
	dfs(l,maxpos);
	dfs(maxpos+1,minpos-1);
	dfs(minpos,r); return;
}
int main()
{
	
	freopen("tahort.in","r",stdin);
	freopen("tahort.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
		ma[i][0]=i;
		mi[i][0]=i;
	}
	st();
	/*for(int i=1;i<=n;i++,printf("\n"))
		for(int j=0;j<=3;j++)
		 printf("%d ",ma[i][j]);*/
	//while(1);
	dfs(1,n);
	printf("%d",ans);
	return 0;
}