Lis
(lis.cpp/in/out)

给你一个刚开始是空的序列，我们将数字1到N依次加入到序列中，每次只将单个数字添加到指定的位置

我们想知道每次数字添加（注：指插入）之后，整个序列的LIS(最长上升子序列)的长度是多少

对于每个文件，第一行是一个数字N(1<= N <= 100000)，接下来有N个数字，第k个数字xk表示我们将k加到第xk(0<=
xk <= k-1)个位置上

对于每个样例，输出N行，第i行表示将i加入序列之后的答案

样例：

输入:

3

00 2

输出：

1

1

2

Hint
In the sample, we add three numbers to the sequence, and form three sequences.
a. 1
b. 2 1
c. 2 1 3

如果是单纯的LIS的话，我们用NlogN的算法就能解决这一题

但是题目说还需要插入

但是如果我们知道了最终的位置，能做吗？当然很好做了，一次LIS即可！

所以，先把最终的位置给确定下来

我们来看，不管你前面怎么插入，最后一个的位置肯定就是输入的那个位置！

所以转换一下，把原本的找位置变成找空位（即输入为 a ，就找从左到右的第 a 个空位）

这样我们就可以吧最终每个数的位置给确定下来，然后再一次LIS不就完了！

比如看样例，0 0 2

我们首先确定最后 3 的位置为3（我们改为1基准，所以2+1=3）                 位置：1 2 3

然后确定2的位置，从左到右的第1（0+1=1）个空位，为1                           位置：1 2 3

再确定1的位置，从左到右第1（0+1=1）个空位，为2                                   位置：1 23

所以，最终1~3的位置为 2 1 3 

我们再对位置做一次LIS即可

现在问题就变成了怎么确定最终的位置，前面也说了，数空位，典型的线段树！！！

代码也就出来了

    /*http://blog.csdn.net/jiangzh7 
    By Jiangzh*/  
    #include<cstdio>  
    #include<cstring>  
    #define max(a,b) ((a)>(b)?(a):(b))  
    const int N=100000+10;  
    const int inf=0x3f3f3f3f;  
    int n,a[N],tmp[N],c[N],len;  
    int free[N*4];  
      
    void build_tree(int p,int l,int r)  
    {  
        if(l==r) {free[p]=1;return;}  
        int m=(l+r)>>1;  
        build_tree(p<<1,l,m);  
        build_tree((p<<1)+1,m+1,r);  
        free[p]=free[p<<1]+free[(p<<1)+1];  
    }  
      
    void insert(int p,int l,int r,int cnt,int x)  
    {  
        if(l==r) {free[p]--;a[x]=l;return;}  
        free[p]--;  
        int m=(l+r)>>1;  
        if(free[p<<1]>=cnt) insert(p<<1,l,m,cnt,x);  
        else insert((p<<1)+1,m+1,r,cnt-free[p<<1],x);  
        free[p]=free[p<<1]+free[(p<<1)+1];  
    }  
      
    int find(int a)  
    {  
        int l=1,r=len,mid;  
        while(l<=r)  
        {  
            mid=(l+r)>>1;  
            if(a>c[mid]) l=mid+1;  
            else r=mid-1;  
        }  
        return l;  
    }  
      
    int main()  
    {  
        freopen("lis.in","r",stdin);  
        freopen("lis.out","w",stdout);  
        scanf("%d",&n);  
        for(int i=1;i<=n;i++) scanf("%d",&tmp[i]);  
        build_tree(1,1,n);  
        for(int i=n;i>=1;i--) insert(1,1,n,tmp[i]+1,i);  
        for(int i=1;i<=n;i++)  
        {  
            int k=find(a[i]);  
            len=max(len,k);  
            c[k]=a[i];  
            printf("%d\n",len);  
        }  
        return 0;  
    }