洛谷 P2782 友好城市

// P2782 友好城市 —— ★ 这一版就能 AC
//
// 题意：大河南北两岸各有 N 个位置互不相同的城市，每对友好城市想连一条直线航道。
//       要求任意两条航道**不相交**，问最多能批准几条。
//
// ★★★ 关键一步：**看出这题是 LIS** —— 题单里说「这一步才是 DP 题的真正门槛」。
//   两条航道 `(a₁, b₁)` 和 `(a₂, b₂)`（a 是南岸坐标、b 是北岸坐标）不相交
//   ⟺ **a 和 b 的大小关系一致**（`a₁ < a₂` 且 `b₁ < b₂`，或者反过来）。
//   ⇒ 把所有城市对**按南岸坐标 a 排序**，问题就变成「在 b 这个序列里挑最长的上升子序列」。
//
// ⚠ 而这一步之所以成立，靠的是题面那句「**位置各不相同**」：
//   a 互不相同 ⇒ 排序之后顺序唯一；b 互不相同 ⇒ 严格上升和不下降是同一件事
//   （页面第 ④ 步：那个「一字之差」的坑在这道题上又是**精确的 0**，和
//    [P1439](/sol/p1439/) 一样是**题面保证**的）。
//
// 复杂度 `O(N log N)`（排序 + LIS）。题面 `N ≤ 2 × 10⁵`，`O(N²)` 过不去。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int, int>> c(n);                    // (南岸, 北岸)
    for (auto& p : c) cin >> p.first >> p.second;
    sort(c.begin(), c.end());                       // ★ 按南岸坐标排

    vector<int> tails;
    for (auto& [a, b] : c) {
        auto it = lower_bound(tails.begin(), tails.end(), b);
        if (it == tails.end()) tails.push_back(b);
        else *it = b;
    }
    cout << tails.size() << "\n";
    return 0;
}

// P2782 的参照物：**枚举所有子集**，逐个检查「两两不相交」
//
// ★ 它把题面照抄一遍 —— 一点「排序 + LIS」的巧劲都不用，
//   而这一页要验的恰恰是「看出它是 LIS」这一步对不对。
// ⚠ 只跑得动 `N ≤ 18` 左右。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int, int>> c(n);
    for (auto& p : c) cin >> p.first >> p.second;

    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) if (mask >> i & 1) v.push_back(c[i]);
        bool ok = true;
        for (size_t i = 0; i < v.size() && ok; i++)
            for (size_t j = i + 1; j < v.size() && ok; j++) {
                // 两条航道相交 ⟺ a 的大小关系和 b 的相反
                bool cross = (v[i].first < v[j].first) != (v[i].second < v[j].second);
                if (cross) ok = false;
            }
        if (ok) best = max(best, (int)v.size());
    }
    cout << best << "\n";
    return 0;
}

// P2782 错法一：**忘了排序**，直接对输入顺序里的北岸坐标求 LIS
//
// 「按南岸坐标排序」这一步不是优化，是**把二维问题降成一维**的那一步：
// 排完序之后，「南岸也递增」这个条件才自动满足，剩下的才只是「北岸递增」。
//
// ★ 不排序的话，输入顺序完全是随机的 —— 它算出来的东西和题目问的没有关系。
// ⚠ 而它在**输入本来就按南岸有序**的数据上会蒙对 —— 页面第 ③ 步量了这件事。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int, int>> c(n);
    for (auto& p : c) cin >> p.first >> p.second;
    // ← 少了 sort

    vector<int> tails;
    for (auto& [a, b] : c) {
        auto it = lower_bound(tails.begin(), tails.end(), b);
        if (it == tails.end()) tails.push_back(b);
        else *it = b;
    }
    cout << tails.size() << "\n";
    return 0;
}

// P2782 「错法」：把 `lower_bound` 写成 `upper_bound`
//
// ★★★ 而它在这道题上**又是精确的 0** —— 和 [P1439](/sol/p1439/) 同一个原因：
//   题面写着两岸城市的「位置**各不相同**」⇒ 排序后的北岸坐标序列**没有重复元素**，
//   而[第 22 章第 ⑩ 步](/ch/22-lis/)那个判据说得很清楚：
//   **没有重复元素时，严格上升和不下降是同一件事。**
//
// ⇒ 这是这一轮那条曲线上的**第五个点**，也是第二个「**题面保证**的 0」。
//   ⚠ 而这个 0 同样配了自检（页面第 ④ 步）：放开「位置各不相同」，它当场就分得出来。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int, int>> c(n);
    for (auto& p : c) cin >> p.first >> p.second;
    sort(c.begin(), c.end());

    vector<int> tails;
    for (auto& [a, b] : c) {
        auto it = upper_bound(tails.begin(), tails.end(), b);       // ← 一字之差
        if (it == tails.end()) tails.push_back(b);
        else *it = b;
    }
    cout << tails.size() << "\n";
    return 0;
}

// P2782 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p2782Count`      人看的版本
// `./p2782Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★ 「按南岸排序 + 北岸 LIS」≡ `2ᴺ` 枚举子集逐对验「不相交」；
//   ② ★ 忘了排序会怎样（照题面随机的抓获率）；
//   ③ ★★★ 那个「一字之差」的坑在这道题上是**精确的 0** —— 题面「位置各不相同」保证的；
//      ⚠ 而这个 0 **配了自检**：放开那句约束，它当场就分得出来；
//   ④ ★ `O(N²)` 在题面顶格上是什么概念。

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

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

typedef vector<pair<int, int>> Cities;

/** 正解：按南岸排序 + 北岸 LIS。loose 用 upper_bound；noSort 跳过排序 */
static int solve(Cities c, bool loose = false, bool noSort = false) {
    if (!noSort) sort(c.begin(), c.end());
    vector<int> t;
    for (auto& [a, b] : c) {
        auto it = loose ? upper_bound(t.begin(), t.end(), b) : lower_bound(t.begin(), t.end(), b);
        if (it == t.end()) t.push_back(b);
        else *it = b;
    }
    return (int)t.size();
}
/** 参照物：枚举所有子集，逐对验「不相交」 */
static int brute(const Cities& c) {
    int n = c.size(), best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) if (mask >> i & 1) v.push_back(c[i]);
        bool ok = true;
        for (size_t i = 0; i < v.size() && ok; i++)
            for (size_t j = i + 1; j < v.size() && ok; j++)
                if ((v[i].first < v[j].first) != (v[i].second < v[j].second)) ok = false;
        if (ok) best = max(best, (int)v.size());
    }
    return best;
}

static Cities genPerm(mt19937& rng, int n) {
    vector<int> a(n), b(n);
    iota(a.begin(), a.end(), 0);
    iota(b.begin(), b.end(), 0);
    shuffle(a.begin(), a.end(), rng);
    shuffle(b.begin(), b.end(), rng);
    Cities c(n);
    for (int i = 0; i < n; i++) c[i] = {a[i], b[i]};
    return c;
}
static Cities genDup(mt19937& rng, int n) {
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    shuffle(a.begin(), a.end(), rng);
    Cities c(n);
    for (int i = 0; i < n; i++) c[i] = {a[i], (int)(rng() % (unsigned)max(1, n / 2))};
    return c;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ①②③ 照题面随机 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0, noSort = 0, upper = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            Cities c = genPerm(rng, (int)(rng() % 12) + 1);
            int ok = solve(c);
            if (brute(c) != ok) bad++;
            if (solve(c, false, true) != ok) noSort++;
            if (solve(c, true) != ok) upper++;
        }
        if (!CSV) printf("① %d 组（照题面：两岸坐标各自互不相同，N ≤ 12）："
                         "排序 + LIS vs 2^N 枚举子集不一致 %d 组\n"
                         "② 忘了排序：不同 %d 组\n"
                         "③ 那个「一字之差」的坑（upper_bound）：不同 %d 组 —— **精确的 0**\n",
                         groups, bad, noSort, upper);
        row("perm", {groups, bad, noSort, upper});
    }

    /* ③ 自检：放开「位置各不相同」，upper_bound 当场就分得出来 */
    {
        mt19937 rng(2782u);
        int rounds = 300, upper = 0;
        for (int r = 0; r < rounds; r++) {
            Cities c = genDup(rng, (int)(rng() % 12) + 4);       // ← 违反题面：北岸会重复
            if (solve(c, true) != solve(c)) upper++;
        }
        if (!CSV) printf("③ ⚠ 自检（放开「位置各不相同」，%d 轮）："
                         "upper_bound 和 lower_bound 不同 %d 轮 ⇒ 上面那个 0 不是空壳\n",
                         rounds, upper);
        row("selfcheck", {rounds, upper});
    }

    /* ④ O(N²) 在顶格上是什么概念 */
    {
        ll n = 200000;
        if (!CSV) printf("④ 顶格 N = 2×10^5：O(N²) 要算 %lld 次（4×10^10 量级），"
                         "而 O(N log N) 约 %lld 次 —— 差 %lld 倍\n",
                         n * n, (ll)(n * 18), (ll)(n / 18));
        row("scale", {n * n, (ll)(n * 18), (ll)(n / 18)});
    }
    return 0;
}

// P2782 对拍生成器：`./p2782Gen <seed> [N 上限] [是否允许坐标重复]`
//   默认 `N ≤ 12`、**严格照题面：两岸坐标各自互不相同**。
//
// ★ 第三个参数（默认 0）是给页面第 ④ 步用的**违反题面**的一档 ——
//   题面写着两岸城市「位置各不相同」，而这一档故意让北岸坐标出现重复。
//   ⇒ 它同时干两件事：给「精确的 0」做自检，顺便称一称那句约束的重量
//     （和同一轮 [P1439](/sol/p1439/) 是同一个动作）。
//
// ⚠ 默认 N 压在 12，因为参照物是 `2ᴺ` 枚举子集。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int nHi = argc > 2 ? atoi(argv[2]) : 12;
    int dup = argc > 3 ? atoi(argv[3]) : 0;
    nHi = max(1, min(200000, nHi));

    mt19937 rng(seed * 2654435761u + 2782u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    printf("%d\n", n);
    if (!dup) {
        vector<int> a(n), b(n);
        iota(a.begin(), a.end(), 0);
        iota(b.begin(), b.end(), 0);
        shuffle(a.begin(), a.end(), rng);
        shuffle(b.begin(), b.end(), rng);
        for (int i = 0; i < n; i++) printf("%d %d\n", a[i], b[i]);
    } else {
        vector<int> a(n);
        iota(a.begin(), a.end(), 0);
        shuffle(a.begin(), a.end(), rng);
        for (int i = 0; i < n; i++)
            printf("%d %u\n", a[i], (unsigned)(rng() % (unsigned)max(1, n / 2)));   // ← 北岸会重复
    }
    return 0;
}