洛谷 P1803 凌乱的yyy / 线段覆盖

// P1803 凌乱的yyy / 线段覆盖 —— ★ 这一版就能 AC
//
// ★ 这是第 19 章的第二道例题，而正文已经把算法证完了（第 ⑨~⑫ 步）：
//   **按右端点从早到晚排序，能选就选**，交换论证两行。
//   ⇒ 所以解析页不重复那些，它讲的是**顶格 n = 10⁶ 带来的三件事**。
//
// ⚠ 题面的两个约定，一个字都不能读漏：
//   ① `a_i < b_i`（不存在「一瞬间」的比赛）；
//   ② **上一场结束的时刻可以正好是下一场开始的时刻** ⇒ 代码里写 `l >= last`，不是 `l > last`。
//      ★ 这一条在顶格随机数据上**几乎抓不到**（页面第 ④ 步：坐标 ≤ 10⁶ 时 300 轮只抓 3 次，
//        坐标压到 100 以内就是 300 / 300）—— 正文那个生成器为此把坐标压到了 14。
//
// 读入 2 × 10⁶ 个整数。★ 页面第 ⑤ 步实测了四种读法：这道题**关同步的 cin 就够**
//   （时限 3 秒，而它只要 0.2 秒上下）—— 「读入量大」和「要写快读」是两句话。

#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>> a(n);                 // (右端点, 左端点)
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {r, l};
    }
    sort(a.begin(), a.end());                    // 按右端点从早到晚

    int cnt = 0, last = -1;                      // 坐标 ≥ 0，所以 -1 比任何左端点都小
    for (auto& [r, l] : a)
        if (l >= last) { cnt++; last = r; }      // ★ 是 >=，端点重合不算冲突

    cout << cnt << "\n";
    return 0;
}

// P1803 的**第二个算法**：动态规划 + 二分 —— 它不是用来交的，是用来当参照物的
//
// ★★★ 这一页的主线就在这份文件上：
//   题面 `n ≤ 10⁶`，而正文那个 `2ⁿ` 枚举子集的暴力只跑得动 `n ≤ 20` ——
//   ⇒ **顶格对拍时，那个参照物没了。**
//   而「能跑顶格的参照物」**不必是暴力**：换一个复杂度相同、但选法完全不同的算法就行。
//
// 这一份的选法和贪心毫无关系：
//   按右端点排好之后，`f[i] = max(f[i-1], f[k] + 1)`，
//   其中 `k` 是「右端点 ≤ 第 i 场左端点」的最后一场（二分找）。
//   —— 也就是「第 i 场选不选」的经典 DP（带权区间调度的无权版本）。
//   ★ 它和贪心只共用「按右端点排序」这一步，**选的逻辑一个字都不共享**。
//
// 复杂度 O(n log n)，顶格 10⁶ 跑得动 ⇒ 顶格对拍成立（页面第 ② 步）。
// ⇒ 和同一天那份 [P1223](/sol/p1223/) 凑成一对：
//   那儿的顶格参照物是「同一个算法换个类型」，这儿是「另一个算法」。**两次都不是暴力。**

#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>> a(n);                 // (右端点, 左端点)
    for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; a[i] = {r, l}; }
    sort(a.begin(), a.end());

    vector<int> rs(n + 1, -1);                   // rs[i] = 前 i 场里第 i 场的右端点（1 下标）
    for (int i = 1; i <= n; i++) rs[i] = a[i - 1].first;

    vector<int> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int l = a[i - 1].second;
        // 找最大的 k < i 使 rs[k] <= l —— rs[1..i-1] 是升序的
        int k = (int)(upper_bound(rs.begin() + 1, rs.begin() + i, l) - rs.begin()) - 1;
        f[i] = max(f[i - 1], f[k] + 1);
    }
    cout << f[n] << "\n";
    return 0;
}

// P1803 错法二：按**左端点**排序（开始得早就先上）
//
// 正文第 ⑫ 步已经用小数据的表打过它了（三种排法：按左端点 3 场、按区间短 3 场、按右端点 4 场）。
// 这一页只补一件正文没做的事：**在题面顶格的规模上，它差多少**（页面第 ③ 步那张表）。
//
// ★ 直觉版的反驳：一场从头开到尾的比赛开始得最早，却把整天都占了。

#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>> a(n);                 // (左端点, 右端点)
    for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; a[i] = {l, r}; }
    sort(a.begin(), a.end());                    // ← 按左端点

    int cnt = 0, last = -1;
    for (auto& [l, r] : a)
        if (l >= last) { cnt++; last = r; }
    cout << cnt << "\n";
    return 0;
}

// P1803 错法一：把 `l >= last` 写成 `l > last`（端点重合当成冲突）
//
// 题面写着「参加一个比赛必须善始善终，而且不能同时参加 2 个及以上的比赛」——
// 上一场 14:00 结束、下一场 14:00 开始，算不算「同时」？**题目说不算。**
//
// ★★★ 而它的抓获率**是一条两层的曲线**（页面第 ④ 步实测，n 固定 1000）：
//   坐标上限   14      100      10⁴      10⁶（题面顶格）
//   被抓       300     300      113      **3**   / 300
//   有端点重合 300     300      300      **191** / 300
//   ⇒ 第一层是「输入里到底有没有端点重合」，第二层是「那一对得正好卡在贪心的路上」。
//     顶格那一档 191 轮里只有 3 轮被抓 —— **按第一层去推，会把抓获率高估 60 倍**。
//   ★ 正文那个生成器（`itvGen.cpp`）把坐标压到 14 就是为了这件事，它的注释里写着
//     「坐标范围开到 1e9 …… 对拍就白跑了」—— 这一页把那句话量了出来：
//     **不是白跑，是从 300 掉到 3（100 倍）**。

#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>> a(n);
    for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; a[i] = {r, l}; }
    sort(a.begin(), a.end());

    int cnt = 0, last = -1;
    for (auto& [r, l] : a)
        if (l > last) { cnt++; last = r; }       // ← 这里
    cout << cnt << "\n";
    return 0;
}

// P1803 的读入：2 × 10⁶ 个整数，四种读法差多少
//
// 用法：./p1803Read [n] [csv]      默认 n = 1000000（题面顶格就是它）
//   ★ 它自己造一份 P1803 形状的输入写进临时文件，再 freopen 回 stdin 读四遍 ——
//     不需要喂输入。四遍算出来的答案必须一模一样（csv 里的 same 钉这件事）。
//
// ⚠ 顺序不能换：关掉同步之后 cin 会自己预读一大块，之后再 freopen 换文件，
//   cin 缓冲里剩的就是上一份文件的残渣 ⇒ 「同步开着」那一趟必须排在最前面
//   （这条坑是第 45 章 read.cpp 踩过的，照抄它的顺序）。
//
// ★ 这一份想说的是一个**否定的结论**：这道题的读入**不构成分数线**。
//   [第 6 章 P2367](/sol/p2367/) 要读两千万个数、时限 1 秒 ⇒ 连 scanf 都不够；
//   这道题读两百万个、时限 3 秒 ⇒ 默认 cin 也就零点几秒。
//   **「读入量大」和「要写快读」是两句话，中间隔着时限这把尺子。**

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

static char path[64];
static const int MAXN = 1000006;
static int L[MAXN], R[MAXN];

static void makeData(int n) {
    snprintf(path, sizeof(path), "/tmp/p1803-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260829u);
    fprintf(f, "%d\n", n);
    for (int i = 0; i < n; i++) {
        int a = (int)(rng() % 1000000u);
        int b = a + 1 + (int)(rng() % (unsigned)(1000000 - a));
        fprintf(f, "%d %d\n", a, b);
    }
    fclose(f);
}
static void reopenIn() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

/* 贪心那几行 —— 四趟共用，所以四趟之间的差别只可能来自读入 */
static int finish(int n) {
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) a[i] = {R[i], L[i]};
    sort(a.begin(), a.end());
    int cnt = 0, last = -1;
    for (auto& [r, l] : a) if (l >= last) { cnt++; last = r; }
    return cnt;
}

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int n = argc > 1 ? atoi(argv[1]) : 1000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv") || (argc > 1 && string(argv[1]) == "csv");
    if (argc > 1 && string(argv[1]) == "csv") n = 1000000;
    n = max(1, min(1000000, n));

    makeData(n);
    long long ms[4]; int ans[4];

    /* ① cin，同步开着（大多数人的第一反应）—— 必须排最前面 */
    {
        reopenIn();
        auto t0 = steady_clock::now();
        int m; cin >> m;
        for (int i = 0; i < m; i++) cin >> L[i] >> R[i];
        ans[0] = finish(m);
        ms[0] = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    }
    /* ② cin + sync_with_stdio(false) */
    {
        reopenIn();
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        auto t0 = steady_clock::now();
        int m; cin >> m;
        for (int i = 0; i < m; i++) cin >> L[i] >> R[i];
        ans[1] = finish(m);
        ms[1] = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    }
    /* ③ scanf */
    {
        reopenIn();
        auto t0 = steady_clock::now();
        int m = 0;
        if (scanf("%d", &m) != 1) return 1;
        for (int i = 0; i < m; i++) if (scanf("%d %d", &L[i], &R[i]) != 2) return 1;
        ans[2] = finish(m);
        ms[2] = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    }
    /* ④ 手写快读（fread 整块读进来自己拼数字） */
    {
        reopenIn();
        ipos = ilen = 0;
        auto t0 = steady_clock::now();
        int m = readIntFast();
        for (int i = 0; i < m; i++) { L[i] = readIntFast(); R[i] = readIntFast(); }
        ans[3] = finish(m);
        ms[3] = duration_cast<milliseconds>(steady_clock::now() - t0).count();
    }
    remove(path);

    bool same = (ans[0] == ans[1] && ans[1] == ans[2] && ans[2] == ans[3]);
    if (csv) {
        printf("same,%d\n", same ? 1 : 0);
        printf("ans,%d\n", ans[0]);
        printf("ms,%lld,%lld,%lld,%lld\n", ms[0], ms[1], ms[2], ms[3]);
        return 0;
    }
    const char* names[4] = {"cin（默认，同步开着）", "cin + sync_with_stdio(false)", "scanf", "手写快读（fread）"};
    printf("n = %d，四种读法（含排序和贪心那几行，四趟完全一样）：\n", n);
    long long best = *min_element(ms, ms + 4);
    for (int i = 0; i < 4; i++)
        printf("  %-32s %6lld 毫秒   比最快的慢 %.1f 倍   答案 %d\n",
               names[i], ms[i], best ? (double)ms[i] / best : 1.0, ans[i]);
    printf("四趟答案一致：%s\n", same ? "是" : "**否（这就是 bug）**");
    return 0;
}

// P1803 的度量程序 —— 这一页除耗时以外的数字都出自这一份。
//
// `./p1803Count`      人看的版本
// `./p1803Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★ 三方一致：小数据上「贪心 / DP / 2ⁿ 枚举子集」三个算法逐组比
//      —— 先确认 DP 那份真的对，它才有资格在顶格当参照物；
//   ② ★★★ `l > last`（端点重合当冲突）的**值域曲线**：
//      照题面随机（坐标 ≤ 10⁶）是**精确的 0**，坐标压到几十才现形；
//      顺带数一数「输入里真的存在端点重合」的轮数 —— 两条线要能对上；
//   ③ ★ 按左端点排在**题面顶格形状**上差多少（正文只量过 n ≤ 10 的小数据）；
//   ④ ★★ 题面那句 `a < b` 是情报 / 命门 / 噪声？判据是造一档**违反它**的数据，
//      看有没有任何一版的行为变了。

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

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

struct Seg { int l, r; };

/** 正解：按右端点排，能选就选（端点重合不算冲突） */
static int greedy(vector<Seg> a, bool strict = false) {
    sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.r < y.r; });
    int cnt = 0, last = -1;
    for (auto& s : a) {
        if (strict ? s.l > last : s.l >= last) { cnt++; last = s.r; }
    }
    return cnt;
}

/** 错法二：按左端点排 */
static int byLeft(vector<Seg> a) {
    sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.l < y.l; });
    int cnt = 0, last = -1;
    for (auto& s : a) if (s.l >= last) { cnt++; last = s.r; }
    return cnt;
}

/** 第二个算法：按右端点排 + DP + 二分（和贪心只共用排序那一步） */
static int dp(vector<Seg> a) {
    int n = a.size();
    sort(a.begin(), a.end(), [](const Seg& x, const Seg& y) { return x.r < y.r; });
    vector<int> rs(n + 1, -1), f(n + 1, 0);
    for (int i = 1; i <= n; i++) rs[i] = a[i - 1].r;
    for (int i = 1; i <= n; i++) {
        int k = (int)(upper_bound(rs.begin() + 1, rs.begin() + i, a[i - 1].l) - rs.begin()) - 1;
        f[i] = max(f[i - 1], f[k] + 1);
    }
    return f[n];
}

/** 2ⁿ 枚举子集（正文那个暴力的同一件事），n ≤ 20 */
static int brute(const vector<Seg>& a) {
    int n = a.size(), best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<Seg> pick;
        for (int i = 0; i < n; i++) if (mask >> i & 1) pick.push_back(a[i]);
        sort(pick.begin(), pick.end(), [](const Seg& x, const Seg& y) { return x.r < y.r; });
        bool ok = true;
        for (size_t i = 1; i < pick.size(); i++) if (pick[i].l < pick[i - 1].r) { ok = false; break; }
        if (ok) best = max(best, (int)pick.size());
    }
    return best;
}

/** 造一组：n 场，坐标 ∈ [0, hi]，严格 a < b；allowEq 时允许 a == b（违反题面） */
static vector<Seg> gen(mt19937& rng, int n, int hi, bool allowEq = false) {
    vector<Seg> a(n);
    for (int i = 0; i < n; i++) {
        int l = (int)(rng() % (unsigned)hi);
        int r = allowEq ? l + (int)(rng() % (unsigned)(hi - l + 1))
                        : l + 1 + (int)(rng() % (unsigned)(hi - l));
        a[i] = {l, r};
    }
    return a;
}
/** 输入里存在「某场的右端点 == 另一场的左端点」吗 */
static bool hasTouch(const vector<Seg>& a) {
    unordered_set<int> ls;
    for (auto& s : a) ls.insert(s.l);
    for (auto& s : a) if (ls.count(s.r)) return true;
    return false;
}

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

    /* ① 三方一致（贪心 / DP / 2ⁿ 暴力） */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int n = 1; n <= 12; n++)
            for (int rep = 0; rep < 30; rep++, groups++) {
                vector<Seg> a = gen(rng, n, 14);
                int g = greedy(a), d = dp(a), b = brute(a);
                if (!(g == d && d == b)) bad++;
            }
        if (!CSV) printf("① 三方一致：%d 组（n <= 12，坐标 <= 14），贪心/DP/2^n 暴力不一致 %d 组\n", groups, bad);
        row("three", {groups, bad});
    }

    /* ② l > last 的值域曲线 */
    {
        const int HIS[] = {14, 100, 10000, 1000000};
        vector<long long> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 2654435761u + 17u);
            int bad = 0, touch = 0;
            for (int r = 0; r < 300; r++) {
                vector<Seg> a = gen(rng, 1000, hi);
                if (hasTouch(a)) touch++;
                if (greedy(a, true) != greedy(a)) bad++;
            }
            out.push_back(bad); out.push_back(touch);
            if (!CSV) printf("② n = 1000，坐标 <= %7d：`l > last` 错 %d / 300，输入里存在端点重合的 %d / 300\n",
                             hi, bad, touch);
        }
        row("strictHi", out);
    }

    /* ③ 按左端点排：题面顶格形状上差多少 */
    {
        const int NS[] = {10, 1000, 100000};
        vector<long long> out;
        for (int n : NS) {
            mt19937 rng(n * 40503u + 23u);
            int bad = 0; long long sumG = 0, sumL = 0;
            int rounds = n >= 100000 ? 20 : 200;
            for (int r = 0; r < rounds; r++) {
                vector<Seg> a = gen(rng, n, 1000000);
                int g = greedy(a), l = byLeft(a);
                sumG += g; sumL += l;
                if (g != l) bad++;
            }
            out.push_back(bad); out.push_back(rounds);
            out.push_back((long long)((double)sumG / sumL * 100 + 0.5));
            if (!CSV) printf("③ n = %6d（坐标 <= 10^6）：按左端点排 %d / %d 轮和正解不同，平均场数比 %.2f 倍\n",
                             n, bad, rounds, (double)sumG / sumL);
        }
        row("left", out);
    }

    /* ④ 题面那句 `a < b`：情报 / 命门 / 噪声？造一档违反它的数据看行为变不变 */
    {
        mt19937 rng(777u);
        int diffG = 0, diffD = 0, diffS = 0;
        for (int r = 0; r < 300; r++) {
            vector<Seg> a = gen(rng, 200, 60, true);   // 允许 l == r
            int g = greedy(a), d = dp(a), s = greedy(a, true);
            if (g != d) diffG++;                        // 贪心和 DP 还一致吗
            if (d != g) diffD++;
            if (s == g) diffS++;                        // 那个错法在这一档还是被抓吗
        }
        if (!CSV) printf("④ 允许 l == r（违反题面）300 轮：贪心和 DP 不一致 %d 轮；`l > last` 那版**没**被抓的 %d 轮\n",
                         diffG, diffS);
        row("eq", {diffG, diffD, diffS});
    }
    return 0;
}

// P1803 对拍生成器：`./p1803Gen <seed> [n] [坐标上限]`
//   默认 `n = 1000`、坐标 `≤ 10⁶` —— ★ **就是「照题面随机」的样子**（题面 `0 ≤ a < b ≤ 10⁶`）。
//
// ★ 默认档故意写成「照题面随机」，因为这一页要演示的正是它的盲区：
//   `l >= last` 写成 `l > last` 那个 bug，在这一档上 300 轮只被抓 **3** 次；
//   把坐标上限压到 100，它当场 **300 / 300**（页面第 ④ 步那张表）。
//   ⚠ 而「输入里有没有端点重合」这一档有 **191 / 300** —— 两个数差 60 倍，
//     所以**别拿第一层当抓获率**。
//
// ⚠ 严格按题面造 `a < b`（题面保证不存在「一瞬间」的比赛）——
//   页面第 ④ 步用「违反它」的一档做过判据：那句约束是**噪声**，四个版本行为一个没变。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int n = argc > 2 ? atoi(argv[2]) : 1000;
    int hi = argc > 3 ? atoi(argv[3]) : 1000000;
    n = max(1, min(1000000, n));
    hi = max(1, min(1000000, hi));

    mt19937 rng(seed * 2654435761u + 999u);
    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        int a = (int)(rng() % (unsigned)hi);          // a ∈ [0, hi-1]
        int b = a + 1 + (int)(rng() % (unsigned)(hi - a));   // b ∈ (a, hi]
        printf("%d %d\n", a, b);
    }
    return 0;
}