大秦为您打开题目传送门（

3/1 题目大意

题目的表述十分清楚，他就是让你求字典序最小的最长上升子序列，如果不存在输出 orz 。

注：在某人jdt1010的提示下发现不存在的情况是当 $n=0$ 的时候分值为两分多一点。

3/2 解题思路

方法1：$dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度

我们阅读题目发现，这道题 $n$ 的数据范围非常大，传统的 $O(n^2)$ 算法肯定是用不了。所以开始思考换一种思路。
由于题目数据范围是 $n\le 10^5$ ，所以不难想到使用 $O(n)$ 或者 $O(n\log n)$ 的算法。

我们开始思考：对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。
所以，我们新建立一个 $st$ 数组，表示以 $i$ 结尾的最长上升子序列的结尾最小值，显然 $st$ 数组严格单调递增。
那么我们实际上就只需要维护这个 $st$ 数组，从而去求出 $dp$ 值。

那么问题就变成了：如何维护这个 $st$ 数组呢？

  1. 如果这个 $a[i]$ 直接可以接到我们的LIS后面，那么就直接放到 $st$ 数组后面。
  2. 否则，就把 $st$ 数组中第一个大于等于 $a[i]$ 的数字换成 $a[i]$ 。这样就可以使得 $st$ 数组单调递增。

那么我们就来证明一下这个算法的正确性：

  1. 最优子结构： 算法在每一步都选择当前最优的状态，即通过比较 $a[i]$ 与 $st$ 中的元素来决定加入 $st$ 的位置。这确保了每个位置 $i$ 上的 $dp[i]$ 是以 $i$ 结尾的最长递增子序列的长度。
  2. 子问题的最优解是全局最优解的一部分： 通过遍历整个数组，对每个位置 $i$ 计算以 $i$ 结尾的最长递增子序列的长度。最终 $dp$ 数组中的最大值即为整个数组的最长递增子序列长度。
  3. 状态转移的正确性： 根据 $a[i]$ 与 $st$ 中最后一个元素的比较，更新 $st$ 和 $dp$ 数组的过程保证了递增子序列的正确性。维护 $st$ 数组的目的是确保以 $i$ 结尾的递增子序列的结尾元素的最小值，以便在后续元素中能够更好地扩展。

说人话：这个算法可以通过这道题

那么已经求出了最长上升子序列的长度，还要输出字典序最小的最长上升子序列。（不会已经有人忘记这道题题目问的是什么了罢）

我们既然状态定义的是以 $i$ 结尾的最长上升子序列长度，那么从后往前 for 一遍绝对是最适合这个算法的了。

那么，怎么做到从后往前 for 一遍实现这个算法呢？

  1. 首先，输出要满足是最长上升子序列，所以，当前节点的 $dp$ 值一定要等于当前的 $len$
  2. 从后往前第一个等于当前 $len$ 的一定是最小的数字（一会证明）
  3. 每找到一个满足条件的数，接着要找的数字个数减一，即为：$len=len-1$ 。

那么为什么，从后往前第一个等于当前 $len$ 的一定是最小的数字呢？

证明：

我们假设按照此算法得出的最长上升子序列是：$a_{i_1},\dots,a_{i_x} ,a_{k_x}, \dots,a_{i_{len}}$
但是，真正的答案应该是：$a_{j_1},\dots,a_{j_y} ,a_{k_y}, \dots,a_{j_{len}}$

这两个序列的前面 $[i_1,i_x]$ 和 $[j_1,j_y]$ 完全一样，但是 $k_x$ 和 $k_y$ 不一样。

那么如果

  1. $a_{k_x}>a_{k_y}$ 则正确答案应该会更长，而如果$a_{i_t-1}\ge a_{j_t}$ ，不符合题意
  2. $a_{k_x}<a_{k_y}$ 则正确答案应该也会更长，而如果$a_{i_t-1}\le a_{j_t}$ ，也不符合题意
  3. 相等更不用说了

所以此算法正确

方法2：$dp[i]$ 表示以 $i$ 开头最长上升子序列长度

那么，都反着写过了，正着呢？当然也是可以的。

我们把方法1中的定义全都反过来，就变成了：
$dp[i]$ 表示以 $i$ 开头最长上升子序列长度。
$st$ 数组，表示以 $i$ 开头的最长上升子序列的结尾最大值，显然 $st$ 数组严格单调递减。因为为了让LIS更好延续，开头越小越好。

维护 $st$ 数组就变成了：

  1. 如果这个 $a[i]$ 直接可以接到我们的LIS后面，那么就直接放到 $st$ 数组后面。
  2. 否则，就把 $st$ 数组中第最个小于等于 $a[i]$ 的数字换成 $a[i]$ 。这样就可以使得 $st$ 数组单调递减。

同理可证该算法正确

3/3 题目代码

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

int n;
int a[100010];

int dp[100010];
vector<int >st;

void Input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
}

void Work() {
    st.push_back(a[1]);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] > st[st.size() - 1]) {
            st.push_back(a[i]);
            dp[i] = st.size();
        }
        else {
            int pos = lower_bound(st.begin(), st.end(), a[i]) - st.begin();
            dp[i] = pos + 1;
            st[pos] = a[i];
        }
    }
    vector<int >ans;
    int len = st.size();
    int f = 1;
    for (int i = n; i >= 1; i--) {
        if (dp[i] == len) {
            ans.push_back(a[i]);
            len--;
            f = 0;
        }
    }
    if (f) {
        printf("orz");
        return;
    }
    for (int now = ans.size() - 1; now >= 0; now--) {
        printf("%d ", ans[now]);
    }
}

int main() {
    Input();
    Work();
    return 0;
}

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;

int n;
int a[100010];

int dp[100010];
vector<int >st;

void Input() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
}

int find(int x) {
    int l = 0, r = st.size() - 1, best = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (st[mid] <= x) {
            r = mid - 1;
            best = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return best;
}

void Work() {
    st.push_back(a[n]);
    dp[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        if (a[i] < st[st.size() - 1]) {
            st.push_back(a[i]);
            dp[i] = st.size();
        }
        else {
            int pos = find(a[i]);
            dp[i] = pos + 1;
            st[pos] = a[i];
        }
    }
    vector<int >ans;
    int len = st.size();
    int f = 1, pre = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= i; j--) {
            if (dp[j] == len && a[j] > pre) {
                ans.push_back(a[j]);
                f = 0;
                i = j - 1;
                pre = a[j];
                len--;
                break;
            }
        }
    }
    if (f) {
        printf("orz");
        return;
    }
    for (int now = 0; now < ans.size(); now++) {
        printf("%d ", ans[now]);
    }
}

int main() {
    Input();
    Work();
    return 0;
}