poj 4604 Deque-----2013多校联合赛第一场--1005

做了一天，终于做出来了。。

结题报告：考虑题目的一个简化版本：使双端队列单调上升。对于序列 A 和队列 Q，找到队列中最早出 现的数字Ax，则Ax将 Q 分成的两个部分分别是原序列中以Ax开始的最长上升和最长下降序 列，答案即为这两者之和的最大值。而对于本题，由于存在相同元素，所以只要找到以Ax 为起点的最长不下降序列和最长不上升序列的和，然后减去两个里面出现Ax次数的最小值 即可。

用nlogn的方法求最长上升子序列，不然好像会超时。。

注释已经写不出来了，做了一天，各种调试，已经。。。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int a[100010],dp1[100010],d1[100010];//a[]存数，dp[i]存i之前的数的子序列的最长长度。
int dp2[100010],d2[100010],du1[100010],du2[100010];
int pre[100010];
int n;
int find(int r,int p)
{
	int l=1,m;
	while(l<r){
		m=(l+r+1)>>1;
		if(d1[m]<=p)
			l=m;
		else
			r=m-1;
	}
	return l+1;
}
int find1(int r,int p)
{
	int l=1,m;
	while(l<r){
		m=(l+r+1)>>1;
		if(d2[m]>=p)
			l=m;
		else r=m-1;
	}
	return l+1;
}
int main()
{
	int t,i,j,k;
	scanf("%d",&t);
	while(t--){
		int mx=0;
		scanf("%d",&n);
		for(i=n;i>=1;i--)
			  scanf("%d",&a[i]);
		for(i=0;i<=n;i++)
			du1[i]=1,du2[i]=1;
		  dp1[1]=1;
		  d1[1]=a[1];
		  int len=1;
		  for(i=2;i<=n;i++){
			  if(a[i]>=d1[len]) j=++len;
			  else if(a[i]<d1[1]) j=1;
			  else j=find(len,a[i]);
			  if(d1[j-1]==a[i]) 
				  du1[i]+=du1[pre[j-1]];
			  d1[j]=a[i],dp1[i]=j;
			  pre[j]=i;
		  }
		  dp2[1]=1;
		  d2[1]=a[1];
		  len=1;
		  for(i=2;i<=n;i++){
			if(a[i]<=d2[len]) j=++len;
			else if(a[i]>d2[1]) j=1;
			else j=find1(len,a[i]);
			if(d2[j-1]==a[i]) 
				du2[i]+=du2[pre[j-1]];
			d2[j]=a[i],dp2[i]=j;
			pre[j]=i;
		  }
		  for(i=1;i<=n;i++)
			  if(dp1[i]+dp2[i]-min(du1[i],du2[i])>mx)
			  {
				mx=dp1[i]+dp2[i]-min(du1[i],du2[i]);
			  }
		  printf("%d\n",mx);
	}
}