记录编号	410103	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	hee	是否通过	通过
代码语言	C++	运行时间	0.489 s
提交时间	2017-05-31 00:29:04	内存使用	42.27 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define RG register
#define lowbit ((k)&(-k))
#define rs ((o<<1)|1)
#define ls (o<<1)
#define mid ((l+r)>>1)
#define maxx 1000003
#include<queue>
using namespace std;
int a[maxx],dp[maxx],sum[maxx],n,tree1[maxx*4],tree2[maxx*4];
void Insert1(int o,int l,int r,int p,int num){
	if(l==r){tree1[o]=num;return;}
	if(mid<p)Insert1(rs,mid+1,r,p,num);
	else Insert1(ls,l,mid,p,num);
	tree1[o]=max(tree1[rs],tree1[ls]);
}
void Insert2(int o,int l,int r,int p,int num){
	if(l==r){tree2[o]=num;return;}
	if(mid<p)Insert2(rs,mid+1,r,p,num);
	else Insert2(ls,l,mid,p,num);
	tree2[o]=max(tree2[rs],tree2[ls]);
}
int ask1(int o,int l,int r,int L,int R){
	if(l>=L&&r<=R)return tree1[o];
	if(mid<L)return ask1(rs,mid+1,r,L,R);
	else if(mid>=R)return ask1(ls,l,mid,L,R);
	else return max(ask1(rs,mid+1,r,L,R),ask1(ls,l,mid,L,R));
}
int ask2(int o,int l,int r,int L,int R){
	if(l>=L&&r<=R)return tree2[o];
	if(mid<L)return ask2(rs,mid+1,r,L,R);
	else if(mid>=R)return ask2(ls,l,mid,L,R);
	else return max(ask2(rs,mid+1,r,L,R),ask2(ls,l,mid,L,R));
}
int main(){
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for(RG int i=1;i<=n;++i)scanf("%d",&a[i]),a[i]++;
	dp[1]=sum[1]=1;Insert1(1,0,maxx,a[1],1);
	for(RG int i=2;i<=n;++i){int Max1=ask1(1,0,maxx,0,a[i]-1),Max2=ask2(1,0,maxx,a[i]+1,maxx);
		if(Max1>Max2){
			dp[i]=Max1+1;
			Insert2(1,0,maxx,a[i],dp[i]);
		}
		else dp[i]=Max2+1,Insert1(1,0,maxx,a[i],dp[i]);
	}
	int ans=dp[n];memset(tree1,0,sizeof(tree1));memset(tree2,0,sizeof(tree2));
	memset(dp,0,sizeof(dp));
	dp[1]=sum[1]=1;Insert1(1,0,maxx,a[1],1);
	for(RG int i=2;i<=n;++i){int Max1=ask1(1,0,maxx,a[i]+1,maxx),Max2=ask2(1,0,maxx,0,a[i]-1);
		if(Max1>Max2){
			dp[i]=Max1+1;
			Insert2(1,0,maxx,a[i],dp[i]);
		}
		else dp[i]=Max2+1,Insert1(1,0,maxx,a[i],dp[i]);
	}
	ans=max(ans,dp[n]);cout<<ans;
	return 0;
}/*5
5 3 2 1 2*/