正常的求LIS的方法是用dp来做，时间复杂度为O(n^2),但是面对一些题目的时候这个复杂度就有点高了，就去学了一下nlogn的解法。主要运用到了二分查找，stl里面的lower_bound 也可以。

upper_bound（i） 返回的是键值为i的元素可以插入的最后一个位置（上界） 

lower_bound（i） 返回的是键值为i的元素可以插入的位置的第一个位置（下界）

先贴一发O(n^2)的代码

1 #include 
     
       2 #define fi first 3 #define se second 4 #define pb push_back 5 #define fio ios::sync_with_stdio(false);cin.tie(0); 6 #define pii pair
      
        7 #define vi vector
       
         8 #define vc vector
        
          9 #define mii map
         
          10 #define si(a) scanf("%d",&a)11 #define ss(a) scanf("%s",&a)12 #define sl(a) scanf("%I64d",&a);13 #define slf(a) scanf("%lf",&a);14 #define CLEAR(a,b) memset(a,b,sizeof(a))15 #define pi acos(-1)16 17 const int INF=0x3f3f3f3f;18 const int N=2e5+5;19 20 typedef long long ll;21 typedef double db;22 typedef unsigned long long ull;23 using namespace std;24 int dp[N];25 int num[N];26 int n;27 28 void solve()29 {30     int res=0;31     for (int i=0;i
          
           >n;50 for (int i=0;i
           
            >num[i];53 }54 solve();55 }
           
          
         
        
       
      
     

这个很好理解，对于O(nlogn)的解法我看了一些博客，里面比较重要的就是替换这个操作，每次找到一个比最后一个还要大的值的时候直接加入后面，碰到比最后面小的数字的时候往里面找第一个比它小的数字，替换掉后面一个。（语文不好。。。直接看例子吧）

如2 5 3 4 9 7 8 10 很容易就能看出来它的LIS长度为6，最长的是 2 3 4 7 8 10。 

具体步骤如下，2进入；5比2大，进入；此时因为3比5小，往里找，2比3小，3替换掉5；4比3大，4进入；9比4大，9进入；7比9小，往前找，4比7小，7替换掉9；后面都直接进入，得到LIS序列2 3 4 7 8 10。

O(nlogn)的代码具体如下

1 #include 
     
       2 #define fi first 3 #define se second 4 #define pb push_back 5 #define fio ios::sync_with_stdio(false);cin.tie(0); 6 #define pii pair
      
        7 #define vi vector
       
         8 #define vc vector
        
          9 #define mii map
         
          10 #define si(a) scanf("%d",&a)11 #define ss(a) scanf("%s",&a)12 #define sl(a) scanf("%I64d",&a);13 #define slf(a) scanf("%lf",&a);14 #define CLEAR(a,b) memset(a,b,sizeof(a))15 #define pi acos(-1)16 17 const int INF=0x3f3f3f3f;18 const int N=2e5+5;19 20 typedef long long ll;21 typedef double db;22 typedef unsigned long long ull;23 using namespace std;24 int ans[N];25 int num[N];26 27 int main()28 {29     fio;30     int n;31     cin>>n;32     for (int i=1;i<=n;i++)33         cin>>num[i];34     ans[1]=num[1];35     int len=1;36     for(int i=2;i<=n;i++)37     {38         if(num[i]>ans[len])39             ans[++len]=num[i];40         else41         {42             int pos=lower_bound(ans,ans+len,num[i])-ans;43             ans[pos]=num[i];44         }45     }46     for (int i=1;i<=len;i++)47     {48         cout<
          
           <<" ";49 }50 cout<