Codeforces 486E：LIS of Sequence - 判斷元素在 LIS 中角色

問題描述

給定長度 n 的序列，對每個元素判斷其在所有最長上升子序列 (LIS) 中的角色：

1. 不出現在任何 LIS 中。
2. 出現在至少一個但不全部 LIS 中。
3. 出現在所有 LIS 中（關鍵元素）。

解法：O(n log n) LIS + 反向掃描

1. 正向計算 up[i]：以 i 結尾的 LIS 長度（標準二分法）。
2. 最大 LIS 長度 maxLen = max(up[i])。
3. 反向掃描維護 help[len]：長度為 len 的 LIS 最後一個元素的最小值（即標準 LIS 算法中的尾部值）。同時記錄 ne[len]：實現該長度的某個位置索引。
4. 對位置 i（從後向前）：
    若 up[i] == maxLen：它是某 LIS 末尾。若 help[maxLen] 未設置，則標記為類型 3（唯一）；否則類型 2（多個選擇），並將之前的標記改為 2。
    若 up[i] < maxLen：檢查 a[i] < help[up[i]+1]。若不滿足，類型 1（無法接在後面）。滿足則類似判斷唯一性。
    更新 help[up[i]] = a[i]，ne[up[i]] = i。

參考代碼 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXN = 100010;
const int INF = 1e9;
int n, a[MAXN], up[MAXN], dp[MAXN];
int help[MAXN], ne[MAXN], ans[MAXN];

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        // 正向 LIS 長度
        int len = 0;
        for (int i = 0; i < n; ++i) {
            int pos = lower_bound(dp, dp + len, a[i]) - dp;
            up[i] = pos + 1;
            if (pos == len) dp[len++] = a[i];
            else dp[pos] = a[i];
        }
        // 反向掃描判斷角色
        fill(help, help + len + 2, 0);
        fill(ne, ne + len + 2, -1);
        fill(ans, ans + n, 1); // 默認類型 1
        for (int i = n - 1; i >= 0; --i) {
            int L = up[i];
            if (L == len) { // 可能是 LIS 末尾
                if (help[L] == 0) { ans[i] = 3; ne[L] = i; }
                else { ans[i] = 2; ans[ne[L]] = 2; ne[L] = i; }
                help[L] = a[i];
            } else {
                if (a[i] >= help[L+1]) ans[i] = 1; // 無法接在 L+1 長度前
                else {
                    if (help[L] == 0) { ans[i] = 3; ne[L] = i; }
                    else { ans[i] = 2; ans[ne[L]] = 2; ne[L] = i; }
                    help[L] = a[i];
                }
            }
        }
        for (int i = 0; i < n; ++i) cout << ans[i];
        cout << endl;
    }
    return 0;
}

關鍵點

• up[i] 只依賴前綴，O(n log n) 可得。
• 反向掃描時，help[L] 維護的是「長度 L 的 LIS 最後元素的最小值」，這保證了若 a[i] < help[L+1] 則 i 可以作為長度 L+1 的 LIS 的前驅。
• 同一長度若有多個候選位置，則它們都屬於類型 2（非必經）。

複雜度

• 時間：O(n log n)。
• 空間：O(n)。