记录编号	447172	评测结果	AAAAAAATTT
题目名称	[NOIP 2013]花匠	最终得分	70
用户昵称	+1s	是否通过	未通过
代码语言	C++	运行时间	3.023 s
提交时间	2017-09-09 15:41:40	内存使用	70.68 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[100010],ar[100010],tp[100010],k,re[100010][5];
struct tre{int l,r,ma;}stree[5000500],stree2[5000500];
int mxx(int a,int b){return a>b?a:b;}
void bui(int l,int r,int idx,struct tre *t)
{
	(t+idx)->l=l;
	(t+idx)->r=r;
	(t+idx)->ma=0;
	if(l==r)return;
	int m=(l+r)/2;
	bui(l,m,idx*2,t);
	bui(m+1,r,idx*2+1,t);
}
int qry(int l,int r,int idx,struct tre t[])
{
	if(l>r)return 0;
	if(t[idx].l==0&&t[idx].r==0)return 0;
	if(t[idx].l==l&&t[idx].r==r)return t[idx].ma;
	if(r<=t[idx*2].r)return qry(l,r,idx*2,t);
	else if(l>=t[idx*2+1].l)return qry(l,r,idx*2+1,t);
	else return mxx(qry(l,t[idx*2].r,idx*2,t),qry(t[idx*2+1].l,r,idx*2+1,t));
}
void upda(int nu,int val,int idx,struct tre *tr)
{
	if((tr+idx)->l==0&&(tr+idx)->r==0)return;
	if((tr+idx)->l<=nu&&nu<=(tr+idx)->r)(tr+idx)->ma=mxx((tr+idx)->ma,val);
	upda(nu,val,idx*2,tr);
	upda(nu,val,idx*2+1,tr);
}
int bs(int nu)
{
	int lo=1,hi=k;
	while(lo<hi)
	{
		int md=(lo+hi)>>1;
		if(tp[md]>=nu)hi=md;
		else lo=md+1;
	}
	return hi;
}
int ma()
{
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]++;
		ar[i]=a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)if(a[i]!=a[i-1])tp[++k]=a[i];
	for(int i=1;i<=n;i++)ar[i]=bs(ar[i]);
	bui(1,n,1,stree);
	bui(1,n,1,stree2);
	re[1][0]=re[1][1]=1;
	upda(ar[1],1,1,stree);
	upda(ar[1],1,1,stree2);
	for(int i=2;i<=n;i++)
	{
		int m1=0,m2=0;
		m1=qry(ar[i]+1,n,1,stree2),m2=qry(1,ar[i]-1,1,stree);
		re[i][0]=m1+1;
		re[i][1]=m2+1;
		upda(ar[i],m1+1,1,stree);
		upda(ar[i],m2+1,1,stree2);
	}
	int mx=0;
	for(int i=1;i<=n;i++)mx=mxx(mx,max(re[i][0],re[i][1]));
	printf("%d",mx);
	return 0;
}
int faq=ma();
int main()
{
	return 0;
}