记录编号	45501	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	100
用户昵称	白乐水	是否通过	通过
代码语言	C++	运行时间	0.305 s
提交时间	2012-10-24 10:16:02	内存使用	45.75 MiB

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;

struct node
{
 int l,r,ma,mi;
} tree[2000040];

int ans,n,a[500010],lc[2000040],rc[2000040],tot,root;

int max(int x,int y){if (a[x]>a[y] || (a[x]==a[y] && x>y)) return x; return y;}
int min(int x,int y){if (a[x]<a[y] || (a[x]==a[y] && x>y)) return x; return y;}

void build(int &t,int l,int r)
{
 tot++; t=tot;
 tree[t].l=l; tree[t].r=r;;
 if (l==r) {tree[t].ma=l;tree[t].mi=l;return;}
 int mid=(l+r)/2;
 build(lc[t],l,mid);
 build(rc[t],mid+1,r);
 tree[t].ma=max(tree[lc[t]].ma,tree[rc[t]].ma);
 tree[t].mi=min(tree[lc[t]].mi,tree[rc[t]].mi);
}

int fida(int t,int l,int r)
{
 if (l>r) return n+1;
 if (tree[t].l==l && tree[t].r==r) return tree[t].ma;
 int mid=(tree[t].l+tree[t].r)/2;
 if (r<=mid) return fida(lc[t],l,r);
 else if (mid+1<=l) return fida(rc[t],l,r);
      else return max(fida(lc[t],l,mid),fida(rc[t],mid+1,r));
}

int fixi(int t,int l,int r)
{
 if (l>r) return 0;
 if (tree[t].l==l && tree[t].r==r) return tree[t].mi;
 int mid=(tree[t].l+tree[t].r)/2;
 if (r<=mid) return fixi(lc[t],l,r);
 else if (mid+1<=l) return fixi(rc[t],l,r);
      else return min(fixi(lc[t],l,mid),fixi(rc[t],mid+1,r));
}

void dfs(int l,int r)
{
 if (l>=r) return;
 if (r-l+1<=ans) return;
 if (r-l==1) {if (a[l]<a[r]) {ans=max(ans,2);}return;}
 int ml=fixi(root,l,r);
 int mr=fida(root,l,r);
 if (a[ml]==a[mr]) return;
 if (ml<mr)
  {
   if (a[fida(root,ml,mr-1)]<a[mr] && a[fixi(root,ml+1,mr)]>a[ml])
     if (mr-ml+1>ans) {ans=mr-ml+1;}
   dfs(l,ml-1);
   dfs(mr+1,r);
  }
 else
  {
   dfs(l,mr);
   dfs(mr+1,ml-1);
   dfs(ml,r);
  }
}

int main()
{
 freopen("tahort.in","r",stdin);
 freopen("tahort.out","w",stdout);

 scanf("%d\n",&n);
 for (int i=1;i<=n;i++) scanf("%d",&a[i]);
 a[0]=0;
 a[n+1]=2147483647;
 root=0; tot=0;
 build(root,1,n);
 ans=0;
 dfs(1,n);
 printf("%d\n",ans);

 fclose(stdin);
 fclose(stdout);
 return 0;
}