记录编号	81877	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.411 s
提交时间	2013-11-19 11:27:14	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<deque>
using namespace std;
const int SIZEN=100001;
const int INF=0x7fffffff;
int h[SIZEN]={0};
int n;
int up[SIZEN]={0};
int down[SIZEN]={0};
deque<pair<int,int> > uf;//first是高度second是最优长度
deque<pair<int,int> > df;
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&h[i]);
}
int ans=0;
void DP1(void){
	up[1]=down[1]=1;
	ans=1;
	int i,j;
	for(i=2;i<=n;i++){
		up[i]=down[i]=1;
		for(j=1;j<i;j++){
			if(h[j]<h[i]) up[i]=max(up[i],down[j]+1);
			if(h[j]>h[i]) down[i]=max(down[i],up[j]+1);
		}
		ans=max(ans,up[i]);
		ans=max(ans,down[i]);
	}
}
int find_lastup(deque<pair<int,int> > s,int k,int left,int right){//最后一个比k大的,s递减
	if(left==right) return left;
	int mid=(left+right)>>1;
	if(s[mid+1].first<=k) return find_lastup(s,k,left,mid);
	else return find_lastup(s,k,mid+1,right);
}
int find_lastlow(deque<pair<int,int> > s,int k,int left,int right){//最后一个比k小的,s递增
	if(left==right) return left;
	int mid=(left+right)>>1;
	if(s[mid+1].first>=k) return find_lastlow(s,k,left,mid);
	else return find_lastlow(s,k,mid+1,right);
}
void DP2(void){
	up[1]=down[1]=1;
	uf.push_back(make_pair(INF,0));
	df.push_back(make_pair(0,0));
	ans=1;
	int nowh,nowf;
	int i,j;
	for(i=1;i<=n;i++){
		nowh=h[i];
		nowf=0;
		j=find_lastup(uf,h[i],0,uf.size()-1);
		ans=max(ans,uf[j].second+1);
		nowf=max(nowf,uf[j].second+1);
		/*for(j=uf.size()-1;j>=0;j--){
			if(uf[j].first>h[i]){
				ans=max(ans,uf[j].second+1);
				nowf=max(nowf,uf[j].second+1);
				break;
				//高度h[i],长度uf[j].second+1			
			}
		}*/
		while(df.size()&&df.back().second<=nowf&&df.back().first>nowh) df.pop_back();
		if(df.size()&&df.back().first<=nowh&&df.back().second>=nowf) ;
		else df.push_back(make_pair(nowh,nowf));
		nowf=0;
		j=find_lastlow(df,h[i],0,df.size()-1);
		ans=max(ans,df[j].second+1);
		nowf=max(nowf,df[j].second+1);
		/*for(j=df.size()-1;j>=0;j--){
			if(df[j].first<h[i]){
				ans=max(ans,df[j].second+1);
				nowf=max(nowf,df[j].second+1);
				break;
			}
		}*/
		while(uf.size()&&uf.back().second<=nowf&&uf.back().first<nowh) uf.pop_back();
		if(uf.size()&&uf.back().first>=nowh&&uf.back().second>=nowf) ;
		else{
			uf.push_back(make_pair(nowh,nowf));
		}
	}
}
int main(){
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
	read();
	//DP2();
	if(n<=10000) DP1();
	else DP2();
	printf("%d\n",ans);
	return 0;
}