[poj 1533]最长上升子序列nlogn树状数组

题目链接：http://poj.org/problem?id=2533

其实这个题的数据范围n^2都可以过，只是为了练习一下nlogn的写法。

最长上升子序列的nlogn写法有两种，一种是变形的dp，另一种是树状数组。

变形的dp可以参考http://www.cnblogs.com/itlqs/p/5743114.html

树状数组的写法其实就是用到了树状数组求前缀最值，必要的时候可以离散化一下。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=10005;
int tree[maxn];
int N;

int lowbit(int x)
{
    return x&-x;
}
void update(int k,int x)
{
    while (k<=N)
    {
        tree[k]=max(tree[k],x);
        k+=lowbit(k);
    }
}
int query(int k)
{
    int res=0;
    while (k)
    {
        res=max(res,tree[k]);
        k-=lowbit(k);
    }
    return res;
}
void init(int n)
{
    N=n;
    for (int i=1;i<=N;i++) tree[i]=0;
}

int a[1005];

int main()
{
    int n;
    scanf("%d",&n);
    init(10001);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]++;
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        int t=query(a[i]-1)+1;
        ans=max(ans,t);
        update(a[i],t);
    }
    printf("%d
",ans);
    return 0;
}

 而真正比赛的时候不会出的这么赤裸裸的。对于树状数组的写法，一般都是会考查离散化的。而对于第一种写法http://www.cnblogs.com/itlqs/p/5743114.html，一般会考查对于这个更新过程的理解。比如这道题：https://loj.ac/problem/6088