hdu4604 deque

时间:2023-03-08 17:09:00

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4604

思路:就是模拟一下,求每一个开始的非上升和非下降序列。然后求重复的数,由于求出来可能不会是我们想要的序列如22221122233

这样的话求出来的会是2222222 222222233,而我们想要的到的是112222,所以不能用普通的,而是用N*logN(当然也是因为数列太长),而我们得到的是1122222多处一个2这个2是11之前留下的,但是因为2比1大才留下,那么2一定会留在最长上升里面,所以2是会被算作重复的减掉。

代码:

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 100010
#define INF 1000000007
#define FI first
#define SE second
using namespace std;
int a[MAXN],f1[MAXN],f2[MAXN],d[MAXN];
int bs(int key,int len)
{
int l,r;
l = ,r = len;
while(l <= r)
{
int mid = (l+r)>>;
if(key >= f1[mid-] && key < f1[mid]) {
//puts("yes");
return mid;
}
else if(key < f1[mid]) r = mid-;
else
l = mid+;
}
}
int bx(int key,int len)
{
int l,r;
l = ,r = len;
while(l <= r)
{
int mid = (l+r)>>;
if(key <= f2[mid-] && key > f2[mid]) return mid;
else if(key > f2[mid]) r = mid-;
else
l = mid+;
}
}
int searchlap(int b[],int val,int len,int s,int t)
{
int l,r,mid;
l = s,r = t;
mid = (l+r)/;
if(b[l] == val && b[r] == val) return r-l+;
else if(l >= r) return ;
else if(b[mid] == val) return +searchlap(b,val,len,l,mid-)+searchlap(b,val,len,mid+,r);
else if(b[mid] > val) return searchlap(b,val,len,l,mid-);
else if(b[mid] < val) return searchlap(b,val,len,mid+,r);
}
int searchlap1(int b[],int val,int len,int s,int t)
{
int l,r,mid;
l = s,r = t;
mid = (l+r)/;
if(b[l] == val && b[r] == val) return r-l+;
else if(l >= r) return ;
else if(b[mid] == val) return +searchlap1(b,val,len,l,mid-)+searchlap1(b,val,len,mid+,r);
else if(val > b[mid]) return searchlap1(b,val,len,l,mid-);
else if (b[mid] > val)return searchlap1(b,val,len,mid+,r);
}
int main()
{
int ncase,n,ans,i,j;
//freopen("text.txt","r",stdin);
scanf("%d",&ncase);
while(ncase--)
{
ans=;
scanf("%d",&n);
int len1,len2;
for( i=;i<n;++i) scanf("%d",&a[i]);
f1[] = -;
f2[] = ;
len1 = len2 = ;
int nowl1,nowl2;
int cnt = ;
int lap1,lap2;
for(i = n-;i >= ;i--)
{
cnt++;
int k;
if(a[i] < f1[]) j = ;
else if(a[i] >= f1[len1]) len1++,j = len1;
else
{
j = bs(a[i],len1);
}
f1[j] = a[i];
lap1 = searchlap(f1,a[i],len1,,len1);
nowl1 = j;
if(a[i] > f2[]) j = ;
else if(a[i] <= f2[len2]) len2++,j=len2;
else
{
j = bx(a[i],len2);
}
f2[j] = a[i];
lap2 = searchlap1(f2,a[i],len2,,len2);
nowl2 = j;
ans = max(ans,nowl1+nowl2-min(lap1,lap2));
}
cout<<ans<<endl;
}
return ;
}