记录编号	45963	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.244 s
提交时间	2012-10-26 00:18:14	内存使用	0.69 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=100010;
int INF,N,Num[MAXN],ans=0;

class SegTree
{
public:
	int l,r,mid,maxp,minp; SegTree *lc,*rc;
	void clear(){maxp=0,minp=0,lc=NULL,rc=NULL;}
}*Root;

inline void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++) 
		scanf("%d",&Num[i]);
	INF=*max_element(Num+1,Num+1+N);INF++;
	Root=new SegTree;
}

void build(SegTree *pnt,int l,int r)
{
	pnt->l=l,pnt->r=r,pnt->mid=(l+r)/2;
	if(l==r) {pnt->maxp=l,pnt->minp=r;return;}
	pnt->lc=new SegTree; build(pnt->lc,l,pnt->mid);
	pnt->rc=new SegTree; build(pnt->rc,pnt->mid+1,r);
	if(Num[pnt->lc->maxp]>=Num[pnt->rc->maxp]) 
		pnt->maxp=pnt->lc->maxp;
		else pnt->maxp=pnt->rc->maxp;
	if(Num[pnt->rc->minp]<=Num[pnt->lc->minp])
		pnt->minp=pnt->rc->minp;
		else pnt->minp=pnt->lc->minp;	
}

int FindMax(SegTree *pnt,int l,int r)
{
	if(pnt->l==l&&pnt->r==r) return pnt->maxp;
	if(r<=pnt->mid) return FindMax(pnt->lc,l,r);
	if(l>=pnt->mid+1) return FindMax(pnt->rc,l,r);
	int a=FindMax(pnt->lc,l,pnt->mid);
	int b=FindMax(pnt->rc,pnt->mid+1,r);
	if(Num[a]>=Num[b]) return a;return b;
}
int FindMin(SegTree *pnt,int l,int r)
{
	if(pnt->l==l&&pnt->r==r) return pnt->minp;
	if(r<=pnt->mid) return FindMin(pnt->lc,l,r);
	if(l>=pnt->mid+1) return FindMin(pnt->rc,l,r);
	int a=FindMin(pnt->lc,l,pnt->mid);
	int b=FindMin(pnt->rc,pnt->mid+1,r);
	if(Num[b]<=Num[a]) return b;return a;
}

void dfs(int l,int r)
{
	if(l>=r) return;
	int big=FindMax(Root,l,r);
	int small=FindMin(Root,l,r);
	if(big>small) 
	{
		if(big-small+1>ans) ans=big-small+1;
		dfs(l,small); dfs(big,r); return;
	}
	if(big==small) return;
	dfs(l,big); dfs(big+1,small-1); dfs(small+1,r);
}

int main()
{
	freopen("tahort.in","r",stdin);
	freopen("tahort.out","w",stdout);
	init(); build(Root,1,N); dfs(1,N);
	printf("%d\n",ans);
	return 0;
}