HDU 4604 Deque(最长上升子序)

本来就对N*log(N)算法不大会....然后各种跪了，求出最长不下降+最长不上升-最少相同元素。求相同元素，用二分求上界搞的。代码里4个二分....
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cmath>
  5 #include <algorithm>
  6 using namespace std;
  7 int d[200001];
  8 int dd[200001];
  9 int f[200001];
 10 int a[200001];
 11 int same[200001];
 12 int n;
 13 int bin1(int size,int x)
 14 {
 15     int l = 0,r = size-1,mid;
 16     while(l <= r)
 17     {
 18          mid = (l+r)/2;
 19         if(x >= f[mid-1]&&x < f[mid])
 20         return mid;
 21         else if(x < f[mid]) r = mid-1;
 22         else l = mid + 1;
 23     }
 24     return mid;
 25 }
 26 int binx(int size,int x)
 27 {
 28     int str = 0,end = size-1,mid;
 29     while(str < end)
 30     {
 31         mid = (str+end)/2;
 32         if(f[mid] < x)
 33         str = mid + 1;
 34         else
 35         end = mid;
 36     }
 37     return str;
 38 }
 39 void LIS1()
 40 {
 41     int i,j,size = 1,k;
 42     f[0] = a[0];d[0] = 1;
 43     same[0] = 1;
 44     for(i = 1;i < n;i ++)
 45     {
 46         if(a[i] < f[0])
 47         {
 48             j = 0;
 49             k = 0;
 50         }
 51         else if(a[i] >= f[size-1])
 52         {
 53             j = size ++;
 54             k = binx(size,a[i]);
 55         }
 56         else
 57         {
 58             j = bin1(size,a[i]);
 59             k = binx(size,a[i]);
 60         }
 61         f[j] = a[i];d[i] = j + 1;
 62         same[i] = min(same[i],j-k+1);
 63     }
 64 }
 65 int bin2(int size,int x)
 66 {
 67     int l = 0,r = size-1,mid;
 68     while(l <= r)
 69     {
 70         mid = (l+r)/2;
 71         if(x <= f[mid-1]&&x > f[mid])
 72         return mid;
 73         else if(x > f[mid]) r = mid-1;
 74         else l = mid + 1;
 75     }
 76     return mid;
 77 }
 78 int bins(int size,int x)
 79 {
 80     int str = 0,end = size-1,mid;
 81     while(str < end)
 82     {
 83         mid = (str+end)/2;
 84         if(f[mid] > x)
 85         str = mid + 1;
 86         else
 87         end = mid;
 88     }
 89     return str;
 90 }
 91 void LIS2()
 92 {
 93     int i,j,size = 1,k;
 94     f[0] = a[0];d[0] = 1;
 95     same[0] = 1;
 96     for(i = 1;i < n;i ++)
 97     {
 98         if(a[i] > f[0])
 99         {
100             j = 0;
101             k = 0;
102         }
103         else if(a[i] <= f[size-1])
104         {
105             j = size ++;
106             k = bins(size,a[i]);
107         }
108         else
109         {
110             j = bin2(size,a[i]);
111             k = bins(size,a[i]);
112         }
113         f[j] = a[i];d[i] = j + 1;
114         same[i] = min(same[i],j - k + 1);
115     }
116 }
117 int main()
118 {
119     int t,i;
120     scanf("%d",&t);
121     while(t--)
122     {
123         scanf("%d",&n);
124         for(i = 0;i < n;i ++)
125         {
126             scanf("%d",&a[i]);
127             same[i] = 1000000;
128         }
129         for(i = 0;i < n/2;i ++)
130         swap(a[i],a[n-i-1]);
131         memset(d,0,sizeof(d));
132         memset(f,0,sizeof(f));
133         LIS1();
134         for(i = 0;i < n;i ++)
135         {
136             dd[i] = d[i];
137         }
138         memset(d,0,sizeof(d));
139         memset(f,0,sizeof(f));
140         LIS2();
141         int maxz = 0;
142         /*for(i = 0;i < n;i ++)
143         {
144             printf("%d ",dd[i]);
145         }
146         printf("
");
147         for(i = 0;i < n;i ++)
148         {
149             printf("%d ",d[i]);
150         }
151         printf("
");
152         for(i = 0;i < n;i ++)
153         {
154             printf("%d ",same[i]);
155         }
156         printf("
");
157         */
158         for(i = 0;i < n;i ++)
159         maxz = max(maxz,dd[i]+d[i]-same[i]);
160         printf("%d
",maxz);
161     }
162     return 0;
163 }