1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 using namespace std;12 const double eps = 1e-8;13 const int INF=0x7fffffff;14 #define MAXN 1000215 16 int main()17 {18 int a[MAXN];19 int n;20 int g[MAXN];21 int up[MAXN],down[MAXN];22 while(scanf("%d",&n)!=EOF)23 {24 for(int i=0;i
               
                =0;i--)37 {38 int k=lower_bound(g+1,g+n+1,a[i])-g;39 down[i]=k;40 g[k]=a[i];41 }42 43 for(int i=0;i
               
              
             
            
           
          
         
        
       
      
     

刘汝佳的 O(nlogn) 的 LIS 算法

lower_bound（first,last,value）在first和last中的前闭后开区间进行二分查找，返回大于或等于value的第一个元素位置。如果所有元素都小于val，则返回last的位置。