SGU 199 Beautiful People：二維 LIS（排序 + 一維 LIS）

核心轉化

1. 按 x 升序排序，x 相同按 y 降序（避免同 x 互相轉移）
2. 問題轉化為：在排序後的序列上，求 y 的嚴格遞增最長子序列（LIS）

LIS O(n log n) 算法

維護 dp[len] = 長度為 len 的 IS 結尾最小 y 值。遍歷每個 y，二分查找在 dp 中的位置 pos，更新 dp[pos]=y。同時記錄 pre[i] 重構路徑。

完整代碼

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

struct Person { int x, y, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        vector<Person> a(n+1);
        for (int i=1; i<=n; i++) {
            cin >> a[i].x >> a[i].y;
            a[i].id = i;
        }
        sort(a.begin()+1, a.end(), [](Person p, Person q) {
            if (p.x != q.x) return p.x < q.x;
            return p.y > q.y; // 同 x 降序 y
        });
        
        vector<int> dp(n+1, INT_MAX), pre(n+1, -1), dpIdx(n+1, -1);
        dp[0] = INT_MIN;
        int len = 0;
        
        for (int i=1; i<=n; i++) {
            int l=1, r=len, pos=len+1;
            while (l <= r) {
                int m = (l+r)/2;
                if (a[dpIdx[m]].y < a[i].y) { pos = m; l = m+1; }
                else r = m-1;
            }
            dpIdx[pos] = i;
            pre[i] = dpIdx[pos-1];
            if (pos > len) len = pos;
        }
        
        cout << len << '\n';
        // 重構路徑
        vector<int> path;
        for (int i=dpIdx[len]; i!=-1; i=pre[i]) path.push_back(a[i].id);
        reverse(path.begin(), path.end());
        for (int i=0; i

關鍵點

同 x 降序 y：保證同 x 的人不會出現在同一 IS 中（因 y 遞減，不滿足嚴格遞增）
dp 存索引而非值，方便重構路徑
二分查找 lower_bound 邏輯：找最大 pos 使 dp[pos-1] < y
輸出原始索引 id，按鏈順序


複雜度
排序 O(n log n)，LIS O(n log n)，總 O(n log n)，n=1e5 通過。