SHU OJ 1936：二維最長遞增子序列 (排序 + LIS)

問題描述

給定兩個長度 N (≤100000) 的數組 A, B。求最長下標序列 D，滿足：A[D[i]] < A[D[i+1]] 且 B[D[i]] > B[D[i+1]]。即 A 嚴格遞增、B 嚴格遞減。

轉化為一維 LIS

1. 將點 (A[i], B[i]) 按 A 升序、A 相同時按 B 升序排序。
2. 對排序後的 B 序列求**嚴格遞減**最長子序列（或取反求嚴格遞增 LIS）。

證明：排序後 A 已非遞減，同 A 值按 B 升序，保證同 A 不會被同時選入嚴格遞增序列（因 B 需遞減）。

O(N log N) LIS 算法

維護 tails 數組，tails[len] 為長度 len 遞增子序列的最小結尾。對每個 x = -B[i]（或直接求遞減）：

• pos = lower_bound(tails, x)（嚴格遞增用 lower_bound）。
• tails[pos] = x。

參考代碼 (C++)

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N) {
        vector> pts(N);
        for (int i = 0; i < N; ++i) cin >> pts[i].first;
        for (int i = 0; i < N; ++i) cin >> pts[i].second;
        sort(pts.begin(), pts.end(), [](auto &a, auto &b) {
            if (a.first != b.first) return a.first < b.first;
            return a.second < b.second; // A相同，B升序
        });
        vector tails;
        for (auto &p : pts) {
            int val = -p.second; // 求B遞減 <=> 求-B遞增
            auto it = lower_bound(tails.begin(), tails.end(), val);
            if (it == tails.end()) tails.push_back(val);
            else *it = val;
        }
        cout << tails.size() << '\n';
    }
    return 0;
}

關鍵細節

• 排序規則：A 升序，**A 相同則 B 升序**。若 B 降序會導致同 A 多個點被錯誤選入。
• N ≤ 100000，必須 O(N log N)，O(N²) 會 TLE。
• 取反轉遞減為遞增，統一用 lower_bound 模板。

總結

• 二維偏序 LIS 經典轉化：一維排序 + 一維 LIS。
• 同鍵值排序順序決定嚴格性，務必仔細推導。
• 大數據量下 vector + lower_bound 效率極高。