最长上升子序列（LIS）

最长上升子序列，全称Longest Increasing Sequence，简称LIS，在计算机科学上是指一个序列中最长的单调递增的子序列（百度百科）。这个序列不一定是连续的。

之前说过，动态规划就是把一个问题分成一大堆子问题，对这些子问题求解，最后求解出这个问题。如何求最长升序列？我们可以想到，随便取一个数字a[i]（当然是在序列里），要是我们知道a[i]之前的且最后一个数据比a[i]小的最长上升子序列长度该多好！直接+1就是以i为结尾的最长上升子序列长度。那么要知道之前的最长升序列长度，就要按照同样的方法找之前的之前……显然是动态规划。

一、普通的DP方法

F[i]=max(F[i],F[j]+1);  (a[i]>a[j] && i>j)

二、二分优化的方法

这里有个问题：替换了序列中的元素，似乎并不能保证替换位置之后的元素在原序列a[i]之后出现？举个栗子：

维护的序列（que数组）：1 3 5 7 9
原序列（a数组）：1 3 5 7 9 4 10（i=6，即现在要处理4这个数字）
本次替换后：1 3 4 7 9

其实替换不会减小序列长度，只会增加序列长度；如果之前把序列中某个元素替换成a[i]，那么之后新加入序列的元素（非替换）肯定都在a[i]之后！que序列并不是真正的最长上升序列，但是长度一定与真正的最长上升序列相等！这么优化可以把时间复杂度优化到O（Nlog2（N））。

代码（新鲜出炉的！！！）：

#include
#include
#include
using namespace std;
const int maxn=100005;
int n,a[maxn],que[maxn],len=0;
inline int read(){
 int ret=0,f=1;char ch=getchar();
 while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
 while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
 return ret*f;
}
inline int find(int x){
 int L=1,R=len;
 while (L<=R){
  int mid=((R-L)>>1)+L;
  if (que[mid-1]