[ CodeVS冲杯之路 ] P3955

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/3955/

　　最长上升子序列的加强版，n 有1000000，n 方的 DP 肯定会 TLE，那么用二分栈维护

　　二分栈我讲不好啊，交给他吧

　　http://www.cnblogs.com/Booble/archive/2010/11/27/1889482.html

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 using namespace std;
 8 
 9 const int N=1000001;
10 int a[N];
11 inline int find(int x,int l,int r)
12 {
13     if (l>=r) return l;
14     int mid=(l+r)>>1;
15     return a[mid]>=x?find(x,l,mid):find(x,mid+1,r);
16 }
17 int main()
18 {
19     int n,m=0,x;
20     scanf("%d",&n);
21     while (n--)
22     {
23         scanf("%d",&x);
24         a[x>a[m]?++m:find(x,1,m)]=x;
25     }
26     printf("%d\n",m);
27     return 0;
28 }