从后向前对已搜点做两遍LIS（最长不下降子序列），分别求出已搜点的最长递增、递减子序列长度。这样一直搜到第一个点，就得到了整个序列的最长递增、递减子序列的长度，即最长递减子序列在前，最长递增子序列在后，得到题目所求的双端队列的最长不下降子序列。
注意要去重，当发生替换之后，同种元素在两个序列中的数量不同。为得到最长序列，当然是把少的去掉，留下多的。
5
2 1 2 2 3
1 #include<stdio.h> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 7 const int MAXN=111111; 8 9 vector<int>v1; 10 vector<int>v2; 11 12 int a[MAXN]; 13 14 int main() 15 { 16 int T,n,i; 17 int len1,len2,same,ans; 18 scanf("%d",&T); 19 while(T--) 20 { 21 ans=0; 22 scanf("%d",&n); 23 for(i=0;i<n;i++) 24 scanf("%d",&a[i]); 25 v1.clear(); 26 v2.clear(); 27 for(i=1;i<=n;i++) 28 { 29 int c=lower_bound(v1.begin(),v1.end(),a[n-i])-v1.begin(); 30 int b=upper_bound(v1.begin(),v1.end(),a[n-i])-v1.begin(); 31 if(b==v1.size()) 32 v1.push_back(a[n-i]); 33 else 34 v1[b]=a[n-i]; 35 len1=b+1; 36 same=b-c+1; 37 38 c=lower_bound(v2.begin(),v2.end(),-a[n-i])-v2.begin(); 39 b=upper_bound(v2.begin(),v2.end(),-a[n-i])-v2.begin(); 40 if(b==v2.size()) 41 v2.push_back(-a[n-i]); 42 else 43 v2[b]=-a[n-i]; 44 len2=b+1; 45 same=min(same,b-c+1);//去重 46 ans=max(len1+len2-same,ans); 47 } 48 printf("%d ",ans); 49 } 50 return 0; 51 }