当前位置：首页 > news >正文

[模板] LIS

news 来源：原创 2024/5/3 20:08:16

树状数组优化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;
}