原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=5748

/*

对于普通的LIS：

for(i):1~n LIS[i]=1;

if j<i and a[j]<a[i]

LIS[i]=LIS[j]+1

因此可知LIS转移需要两个条件

1.(j<i) 序号必须在i之前

2.(a[i]>a[j]) 值必须比a[i]小

利用树状数组的顺序操作：{查找的都是已经出现的,序号在前(满足条件1)}

对于每一个值,查找它在数组中的排名,再去寻找小于它的排名的最大的LIS(满足条件2)

这里利用到了排名,因为这样可以最大限度地压缩C数组的空间

*/

#include <bits/stdc++.h>

using namespace std;

const int Max=1e5+;

int A[Max],V[Max],L[Max],C[Max],len;

int lowbit(int x) {return x&(-x);}

int Sum(int x)           //求值小于等于x的LIS的最大值

{

    int ret=;

    while(x>)

    {

        if(C[x]>ret) ret=C[x];

        x-=lowbit(x);

    }

    return ret;

}

void Add(int x,int d)   //值大于等于x的LIS都改为LIS(x)

{

    while(x<=len)

    {

        if(d>C[x]) C[x]=d;

        x+=lowbit(x);

    }

}

int main()

{

    int T;

    for(scanf("%d",&T);T;T--)

    {

       int n;

       scanf("%d",&n);

       for(int i=;i<=n;i++)

       {

          scanf("%d",&A[i]);

          V[i]=A[i];

       }

       sort(V+,V++n);

       len=unique(V+,V++n)-(V+);

       memset(C,,sizeof(C));

       int ans=,tmp,xu;

       for(int i=;i<=n;i++)

       {

           xu=lower_bound(V+,V++len,A[i])-(V);

           tmp=Sum(xu-)+;

           L[i]=tmp;

           Add(xu,tmp);

       }

       for(int i=;i<=n;i++)

       {

          if(i!=) printf(" ");

          printf("%d",L[i]);

       }

       puts("");

    }

    return ;

}

/*

以dp[x]代表长度为x的LIS,且dp[x]==LIS长度为x的末尾值

每次都往前取dp[x]中最小的一个,当然在保证x尽可能地大的情况下

因为dp[x]是递增的，所以可以二分,l=1,r=当前最长的LIS

求得当前以小于当前a[i]的最长LIS

*/

#include <bits/stdc++.h>

using namespace std;

const int Max=1e5+;

int A[Max];

int dp[Max];

int LIS[Max];

void Get_lis(int n)

{

    int i,j,l,r,mid,ans;

    dp[]=A[];

    int len=;

    for(i=;i<=n;i++)

    {

        if(dp[len]<A[i]) j=++len;

        else

        {

            l=;r=len;

            ans=;

            while(l<=r)

            {

                mid=(l+r)>>;

                if(A[i]>dp[mid]&&A[i]<=dp[mid+])

                {

                    ans=mid;break;

                }

                else if(A[i]>dp[mid]) l=mid+;

                else r=mid-;

            }

            j=ans+;

        }

        dp[j]=A[i];

        LIS[i]=j;

    }

}

int main()

{

    int T;

    for(scanf("%d",&T);T;T--)

    {

        int n;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&A[i]);

            dp[i]=;

        }

        LIS[]=;

        Get_lis(n);

        for(int i=;i<=n;i++)

        {

            if(i!=) printf(" ");

            printf("%d",LIS[i]);

        }

        puts("");

    }

    return ;

}

/*

无解。。。

单调队列只能求出总体的LIS长度

*/

#include <bits/stdc++.h>

using namespace std;

const int Max=1e5+;

int que[Max];

int main()

{

    int T;

    for(scanf("%d",&T);T;T--)

    {

        int n,x,top=;

        scanf("%d",&n);

        for(int i=;i<n;i++)

        {

            scanf("%d",&x);

            if(x>que[top]||top==)

            {

                que[++top]=x;

            }

            else

            {

                int l=,r=top,mid,ans;

                ans=;

                while(l<=r)

                {

                    mid=l+(r-l)/;

                    if(que[mid]<x) l=mid+;

                    else r=mid-,ans=mid;

                }

                que[ans]=x;

            }

        }

        cout<<top<<endl;

    }

    return ;

}