[模板] LIS

树状数组优化LIS到nlogn，网上找了好多，感觉讲得都不是很明白，正好自己复习整理一下。

基本的DP方程 f[i]=max(f[i],f[j]+1) (j<i且a[j]<a[i])

定义一个数组b

以a[i]为下标

存储 以a[i]结尾的最长上升子序列长度

例如序列 5 2 1 3 4

最终b数组如下

i	1	2	3	4	5
b	1	1	2	3	1

定义它有什么好处呢？

每次转移f[i]，是找f[j]的过程，有两个条件：

1. f[j]最大值

2. j<i

第二个j<i好说，用循环卡范围在[1,i-1]即可。

那第一个条件呢？a在[1,i-1]的最大值，区间最值，RMQ问题？

用什么呢？ST表？不行，我们要更改。

注意到这个区间一定是一个前缀区间，那树状数组呢？树状数组本质是求前缀和的，当然可以改造成求前缀最大值啦。

void query(int now){

    int ret=0;

    while(now){

        ret=max(ret,t[now]);

        now-=now&-now;

    }

    return ret;

} 

void updata(int now,int w){

    while(now<=n){

        t[now]=max(t[now],w);

        now+=now&-now;

    }

}

再具体考虑一下转移，先考虑限制a[j]<a[j]的问题

把a数组离散化，1-n个下标对应1-n个数

定义v为a[i]

那就是求出b[1],b[2],… ,b[v-1]的最大值，这个可以用树状数组。

那j<i的问题呢？

换言之，b[1~v-1]是可以求最大值，那怎么*保证这些比a[i]小的数一定在i前面*呢？

答案是：不需要保证。

在i前面的数，之前已经更新过，所以b数组中这些数有了值，而i之后的数，尚未访问过，就是0。

0是不影响最大值的。

所以，我们的大体思路已经成型了：

求出b[1],b[2],…,b[v-1]的最大值
用这个最大值+1更新b[v]

再次强调上述的v是里当前正在更新的那个数，也就是a[i]，i是下标，v是树状数组的下标。

所以，这个b数组不需要真实存在，用树状数组假装它存在，实际上维护前缀最大值就行。

复杂度估计一下，循环遍历n个数，每次找前缀最大值logn，合计O(nlogn)

//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=20000;

int a[MAXN],tmp[MAXN],f[MAXN];

int n;

int t[MAXN];

inline void updata(int now,int w){

    while(now<=n){

        t[now]=max(t[now],w);

        now+=now&-now;

    }

}

inline int query(int now){

    int ret=0;

    while(now){

        ret=max(ret,t[now]);

        now-=now&-now;

    }

    return ret;

}

int main(){

    cin>>n;

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

        cin>>a[i];

        tmp[i]=a[i];

    }

    sort(tmp+1,tmp+1+n);

    int tot=unique(tmp+1,tmp+1+n)-tmp;

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

        a[i]=lower_bound(tmp+1,tmp+1+tot,a[i])-tmp;

    int ans=1;

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

        f[i]=query(a[i]-1)+1;

        updata(a[i],f[i]);

        ans=max(f[i],ans);

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

[模板] LIS

最新文章

热门文章