nlogn求LIS（树状数组）

之前一直是用二分

但是因为比较难理解，写的时候也容易忘记怎么写。

今天比赛讲评的时候讲了一种用树状数组求LIS的方法

(1)好理解，自然也好写（但代码量比二分的大）

(2)扩展性强。这个解法顺带求出以i为结尾的LIS，而很多题要用到这个数组来做

而二分的做法求得是当前长度下的最小值，不容易拓展。

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1e3 + ;

int a[MAXN], b[MAXN], n, m, ans;

int dp[MAXN], f[MAXN];

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

void motify(int x, int p)

{

    for(; x <= m; x += lowbit(x))

        f[x] = max(f[x], p);

}

int get_max(int x)

{

    int res = ;

    for(; x; x -= lowbit(x))

        res = max(res, f[x]);

    return res;

}

int main()

{

    scanf("%d", &n);

    _for(i, , n) scanf("%d", &a[i]), b[i] = a[i];

    sort(b + , b + n + );

    m = unique(b + , b + n + ) - b - ;

    _for(i, , n) a[i] = lower_bound(b + , b + m + , a[i]) - b;

    int ans = ;

    _for(i, , n)

    {

        dp[i] = get_max(a[i] - ) + ;

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

        motify(a[i], dp[i]);

    }

    printf("%d\n", ans);

    return ;

}

具体怎么做呢

n方的算法有一步去枚举之前所有的元素比较耗时间

可以用树状数组优化这一步，树状数组维护区间最大值

把元素的值当作下标，dp值作为值

a[i]表示当前值，dp[i]表示以i为结尾最长不下降子序列的长度

则 dp[i] = get_max(a[i]) + 1

也就是说，在小于等于当前值a[i]中，最大的dp值+1就是当前的答案

不过这里有个细节，怎么区分最长不下降还是最长上升？

如果你对原理理解透彻的话，这个问题其实很容易解决，你可以停下来自己推一下，检验一下自己理解了没有

如果是最长不下降的话，dp[i] = get_max(a[i]) + 1

如果最长上升的话， dp[i] = get_max(a[i]-1) + 1

最后注意要离散化一下

以下是最长上升子序列的模板

巴特西

nlogn求LIS（树状数组）

最新文章

热门文章