LIS：最长上升子序列

dongzirui0817 · 2025-10-26 12:29:26 · 算法·理论

Update on 2026.9.13：新增了 5 道例题。

本来想加 [ABC360G] Suitable Edit for LIS 的，但是这题似乎没有只用 LIS 就能解决的方案，题解区里唯一只用 LIS 的题解还被 hack 了。算鸟不加了，给感兴趣的读者食用。

LIS，即最长上升子序列。相信你们都会 O(n^2) 了，这里不讲了。这里讲 O(n\log n)。

LIS 例题

注意下面的做法是严格上升。

我们来考虑一个状态 f_i，表示长度为 i 的最长上升子序列的最后一项最小为多少。

显然越小答案越优，所以这是没问题的。我们考虑现在的最长上升子序列长为 m。现在考虑 A_k。那么：

• 如果 f_m<A_k，那么 f_{m+1} \gets A_k，然后 m \gets m + 1。
• 如果 f_m\ge A_k，那么我们找到最小的满足 f_j\ge A_k 的位置，则：
  • 所以我们就二分找到这个 j，然后 f_j \gets A_k 即可。

使用 lower_bound 可更简洁地找到这个 j。

int n, cnt = 0;
int f[100010];

int main() {
    scanf("%d", &n);
    for (int i = 1, x ; i <= n ; i++) {
        scanf("%d", &x);
        if (x > f[cnt]) f[++cnt] = x;
        else f[lower_bound(f + 1, f + cnt + 1, x) - f] = x;
    }
    printf("%d\n", cnt);
    return 0;
}

:::warning[注意]{open} 当 A_i 不是正数时，f_i 初值要设为负无穷。 :::

现在，我们把它运用在题目当中。

递增

贪心。显然挑出一个 LIS，把剩下的修改就一定可以满足。证明：无需证明。

所以答案就是 n 减最长上升子序列的长度。

金币收集

由于从左往右走，所以考虑按地点排序。直接考虑有点困难，但注意到小 A 站原地越久越容易丢失越多的金币，所以考虑设 p_i 为小 A 到 i 号金币处前，最多在其他地方不动多久。那么如果原地不动时间超过 p_i，就领不到了。

显然 p_i = t_i - x_i。那么发现一个很重要的结论：答案就是以 0 为首项的 p 的最长不降子序列！

该结论不必多说，只是不好发现。

注意：

• 求最长不降子序列时，要用的是 upper_bound。证明可以像 LIS 来证。
• 注意 p_i<0 的情况。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;

int n;
pair <int, int> c[100010];
int f[100010], cnt = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i++)
        scanf("%d%d", &c[i].first, &c[i].second);
    sort(c + 1, c + n + 1);
    for (int i = 1 ; i <= n ; i++) {
        int x = c[i].second - c[i].first;
        if (x < 0) continue;
        if (f[cnt] <= x)
            f[++cnt] = x;
        else f[upper_bound(f + 1, f + cnt + 1, x) - f] = x;
    }
    printf("%d\n", cnt);
    return 0;
}

:::

[ABC134E] Sequence Decomposing

显然这题要求最少的上升子序列，使所有数都被覆盖。

结论：答案为最长不升子序列长度。

这也就是并非大名鼎鼎的 Dilworth 定理：将一个序列剖成若干个单调上升子序列的最少个数等于该序列最长不升子序列的长度。

:::info[有趣的事情]{open}

• 将一个序列剖成若干个上升子序列的最少个数等于该序列最长不升子序列的长度。
• 将一个序列剖成若干个不升子序列的最少个数等于该序列最长上升子序列的长度。
• 将一个序列剖成若干个下降子序列的最少个数等于该序列最长不降子序列的长度。

• 将一个序列剖成若干个不降子序列的最少个数等于该序列最长下降子序列的长度。

证明考虑贪心。设 f_i 表示第 i 个子序列的末项，对于一个为 x 的数，我们让满足 f_i < x 的最小的 i 来接这个 x。如果不存在这样的 i 就再创一个子序列来接这个 x。

显然这样构造一定是最优的，可以直接二分求解。其实这个过程就是在求最长不升子序列（当然没意识到也无所谓），于是做完了。

小 trick：求降序数组的大于 x 的位置，可以用 upper_bound(f + 1, f + cnt + 1, x, greater <int> ()) 实现。注意初始化 f_i 为正无穷。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;

int n;
int f[100010], cnt = 0;

int main() {
    scanf("%d", &n);
    memset(f, 127, sizeof(f));
    for (int i = 1, x ; i <= n ; i++) {
        scanf("%d", &x);
        if (f[cnt] >= x)
            f[++cnt] = x;
        else f[upper_bound(f + 1, f + cnt + 1, x, greater <int> ()) - f] = x;
    }
    printf("%d\n", cnt);
    return 0;
}

:::

导弹拦截

结论：第一问为最长不升子序列；第二问为最少不升子序列数量，也就是最长上升子序列。

这和上面的那题不一样的吗？双倍经验。

[ABC393F] Prefix LIS Query

回忆一下 LIS 的求法。可以发现，当前 i 个数均被插入时，所有数字都小于等于 X 的 LIS 长度为最小满足 f_i \le X 的 i。

所以如果 R_i 能单调不降，该有多好啊！这样我们就可以通过将 A_i 按顺序插入来求出所有查询啦！

发现查询之间互相独立，考虑把它们离线下来按 R_i 排序，做完了。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;

int n, q, cnt = 0;
int a[200010], c[200010], ans[200010];
vector <pair <int, int>> qu[200010];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1 ; i <= n ; i++) scanf("%d", &a[i]);
    for (int r, x, i = 1 ; i <= q ; i++)
        scanf("%d%d", &r, &x), qu[r].push_back({x, i});
    for (int i = 1 ; i <= n ; i++) {
        if (a[i] > c[cnt]) c[++cnt] = a[i];
        else c[lower_bound(c + 1, c + cnt + 1, a[i]) - c] = a[i];
        for (auto y : qu[i])
            ans[y.second] = upper_bound(c + 1, c + cnt + 1, y.first) - c - 1;
    }
    for (int i = 1 ; i <= q ; i++)
        printf("%d\n", ans[i]);
    return 0;
}

:::

[ABC354F] Useless for LIS

我们希望求出以下值：

此时只要有 f_i+g_i-1=K，那么 i 就是一个正确的答案。