洛谷 P1020 [NOIP 1999 提高组] 导弹拦截

// P1020 [NOIP 1999 提高组] 导弹拦截 —— ★ 这一版就能 AC
//
// 两问：
//   ① 一套系统最多拦几发 = 最长**不上升**子序列的长度（后一发不能高于前一发）；
//   ② 最少要几套系统    = **Dilworth 定理** ⇒ 最长**严格上升**子序列的长度。
//
// ★★★ 这道题是[第 22 章第 ⑩ 步](/ch/22-lis/)那个「一个字母的坑」的**实战版**：
//   **两问用的边界正好相反**：
//     · 第一问「不上升」（允许相等）⇒ 在**降序**的 tails 上用 `upper_bound(..., greater)`；
//     · 第二问「严格上升」（不许相等）⇒ 在**升序**的 tails 上用 `lower_bound`。
//   ⇒ 两个 `bound` 写反任何一个，都只错**一问**（题面开了 SPJ，按问给分）。
//
// ⚠⚠ 而这道题的数据让那个坑**躲不掉**：`n ≤ 10⁵` 而高度 `≤ 5 × 10⁴` ——
//   **n 比值域还大**，鸽巢原理保证一定有重复，而且平均每个高度出现两次。
//   ⇒ 和同一轮那份 [B3637](/sol/b3637/) 正好是两个极端：
//     那道题 `n / 值域 = 0.005`，同一个 bug 300 轮只抓到 2 次；
//     这道题 `n / 值域 = 2.0`，一抓一个准（页面第 ④ 步那张表）。
//
// ⚠ 还有一个和算法无关的坑：**输入不给 n** —— 「一行，若干个整数」，要读到 EOF 为止。
//
// 复杂度 `O(n log n)`。★ `O(n²)` 在 `n = 10⁵` 上本机要 10.8 秒（[B3637](/sol/b3637/) 那页量的）。

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

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

    vector<int> a;
    int x;
    while (cin >> x) a.push_back(x);            // ★ 读到 EOF —— 题面不给 n

    vector<int> down, up;                        // down 保持不增；up 保持严格递增
    for (int v : a) {
        // ① 最长不上升：tails 是不增的，找第一个 **< v** 的位置替换
        auto it = upper_bound(down.begin(), down.end(), v, greater<int>());
        if (it == down.end()) down.push_back(v);
        else *it = v;
        // ② 最长严格上升（Dilworth ⇒ 第二问的答案）
        auto jt = lower_bound(up.begin(), up.end(), v);
        if (jt == up.end()) up.push_back(v);
        else *jt = v;
    }
    cout << down.size() << "\n" << up.size() << "\n";
    return 0;
}

// P1020 错法二：以为第一个数是 n
//
// 题面的输入格式只有一句：「**一行，若干个整数**，中间由空格隔开。」——
// **不给个数**，要读到 EOF 为止。
//
// 而这一版按最常见的格式写：先读一个 n，再读 n 个数。
// ⇒ 它把第一发导弹的高度当成了个数，然后少读一发、还可能读到一堆不存在的数。
// ★ 官方样例第一个数是 389 ⇒ 它会试着读 389 个数，读到 EOF 就停 ——
//   于是它算的是「从第二发开始」的答案（页面第 ⑤ 步量了它错多少）。

#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<int> a;
    for (int i = 0; i < n; i++) { int x; if (!(cin >> x)) break; a.push_back(x); }

    vector<int> down, up;
    for (int v : a) {
        auto it = upper_bound(down.begin(), down.end(), v, greater<int>());
        if (it == down.end()) down.push_back(v);
        else *it = v;
        auto jt = lower_bound(up.begin(), up.end(), v);
        if (jt == up.end()) up.push_back(v);
        else *jt = v;
    }
    cout << down.size() << "\n" << up.size() << "\n";
    return 0;
}

// P1020 的**第二条路**：第二问不用 Dilworth，直接贪心模拟「开几套系统」
//
// ★ 这一份是**参照物**，不是错法：
//   来一发导弹，就在现有的系统里挑一套「当前最低高度 ≥ 它、且最低的那一套」接下它；
//   一套都接不了就新开一套。⇒ 需要几套，就是第二问的答案。
//
// ★★ 它和 Dilworth 那条路**一个字都不共享** —— 那边求的是「最长严格上升子序列」，
//   这边根本没提到「子序列」三个字。两条路给出同一个数，是这一页对第二问的交叉验证。
//
// ⚠ 挑「最低的那一套」要用 multiset（`lower_bound`），复杂度也是 `O(n log n)`。
//   ★ 顺带：这一步挑「恰好够用的那一套」而不是「随便一套」，本身就是一个贪心 ——
//     它的正确性和第 19 章排队接水那套交换论证是同一个味道。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> a;
    int x;
    while (cin >> x) a.push_back(x);

    // 第一问照抄正解（这一份只为第二问提供第二条路）
    vector<int> down;
    for (int v : a) {
        auto it = upper_bound(down.begin(), down.end(), v, greater<int>());
        if (it == down.end()) down.push_back(v);
        else *it = v;
    }

    multiset<int> sys;                            // 每套系统「下一发最高能打多高」
    for (int v : a) {
        auto it = sys.lower_bound(v);             // 第一套「还能打得到 v」的系统
        if (it == sys.end()) sys.insert(v);       // 都打不了 ⇒ 新开一套
        else { sys.erase(it); sys.insert(v); }    // 用它，之后它的上限降到 v
    }
    cout << down.size() << "\n" << sys.size() << "\n";
    return 0;
}

// P1020 错法一：两问的 bound 写反了（两个都写成 lower_bound / 都写成 upper_bound 的变体）
//
// ★★★ 这就是[第 22 章第 ⑩ 步](/ch/22-lis/)那个坑的实战形态：
//   第一问要「不上升」（**允许相等**），第二问要「严格上升」（**不许相等**）——
//   两问的边界**正好相反**，而代码里差的只有一个字母。
//
// 这一版把两问的边界都往「严格」拧：
//   · 第一问用 `lower_bound(..., greater)` ⇒ 求成了「严格下降」，答案偏小；
//   · 第二问用 `upper_bound` ⇒ 求成了「不下降」，答案偏大。
//   ⇒ **两问同时错，而且错的方向相反。**
//
// ⚠ 题面开了 SPJ、按问给分 ⇒ 这一版两问都丢分。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> a;
    int x;
    while (cin >> x) a.push_back(x);

    vector<int> down, up;
    for (int v : a) {
        auto it = lower_bound(down.begin(), down.end(), v, greater<int>());   // ← 拧成严格下降
        if (it == down.end()) down.push_back(v);
        else *it = v;
        auto jt = upper_bound(up.begin(), up.end(), v);                        // ← 拧成不下降
        if (jt == up.end()) up.push_back(v);
        else *jt = v;
    }
    cout << down.size() << "\n" << up.size() << "\n";
    return 0;
}

// P1020 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1020Count`      人看的版本
// `./p1020Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 三条路对第二问给同一个数：Dilworth（最长上升）/ `O(n²)` DP / 贪心模拟开几套系统；
//   ② ★★★ **`n / 值域` 的比值**决定「两问的 bound 写反」抓不抓得到 ——
//      和同一轮 [B3637](/sol/b3637/) 那页正好是同一条曲线的两头；
//   ③ ★ 题面顶格（`n = 10⁵`、高度 ≤ `5×10⁴`）**鸽巢原理保证有重复**：数一数有多少对；
//   ④ ★ 「把第一个数当成 n」那个读入错法的抓获率；
//   ⑤ ★ 两问各自写反一个 bound，会错哪一问（题面按问给分）。

#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");
}

/** 第一问：最长不上升子序列（tails 不增，upper_bound + greater） */
static int longestNonIncr(const vector<int>& a, bool strictBound = false) {
    vector<int> t;
    for (int v : a) {
        auto it = strictBound ? lower_bound(t.begin(), t.end(), v, greater<int>())
                              : upper_bound(t.begin(), t.end(), v, greater<int>());
        if (it == t.end()) t.push_back(v);
        else *it = v;
    }
    return (int)t.size();
}
/** 第二问：最长严格上升子序列（Dilworth） */
static int longestIncr(const vector<int>& a, bool loose = false) {
    vector<int> t;
    for (int v : a) {
        auto it = loose ? upper_bound(t.begin(), t.end(), v) : lower_bound(t.begin(), t.end(), v);
        if (it == t.end()) t.push_back(v);
        else *it = v;
    }
    return (int)t.size();
}
/** O(n²) DP 版：一次求最长不上升，一次求最长严格上升 */
static pair<int, int> byN2(const vector<int>& a) {
    int n = a.size();
    if (!n) return {0, 0};
    vector<int> f(n, 1), g(n, 1);
    int p = 0, q = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] >= a[i]) f[i] = max(f[i], f[j] + 1);      // 不上升
            if (a[j] < a[i]) g[i] = max(g[i], g[j] + 1);       // 严格上升
        }
        p = max(p, f[i]); q = max(q, g[i]);
    }
    return {p, q};
}
/** 贪心模拟：开几套系统 */
static int bySystems(const vector<int>& a) {
    multiset<int> sys;
    for (int v : a) {
        auto it = sys.lower_bound(v);
        if (it == sys.end()) sys.insert(v);
        else { sys.erase(it); sys.insert(v); }
    }
    return (int)sys.size();
}

static vector<int> gen(mt19937& rng, int n, int hi) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = (int)(rng() % (unsigned)hi) + 1;
    return a;
}

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

    /* ① 第二问的三条路 */
    {
        mt19937 rng(20260829u);
        int groups = 0, badN2 = 0, badSys = 0, badN2a = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            vector<int> a = gen(rng, (int)(rng() % 20) + 1, 10);
            auto [p, q] = byN2(a);
            if (longestNonIncr(a) != p) badN2a++;
            if (longestIncr(a) != q) badN2++;
            if (bySystems(a) != q) badSys++;
        }
        if (!CSV) printf("① %d 组：第一问 tails vs O(n²) 不一致 %d 组；"
                         "第二问 Dilworth vs O(n²) 不一致 %d 组；vs 贪心模拟不一致 %d 组\n",
                         groups, badN2a, badN2, badSys);
        row("three", {groups, badN2a, badN2, badSys});
    }

    /* ② ★★★ n / 值域 的比值决定抓不抓得到 */
    {
        // n 固定 2000，只拧值域 ⇒ 比值从 0.002 走到 2.0
        const int HIS[] = {1000000, 20000, 2000, 1000, 200};   // 比值 0.002 / 0.1 / 1 / 2 / 10
        const int N = 2000;
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 7919u + 20u);
            int dup = 0, bad1 = 0, bad2 = 0;
            for (int r = 0; r < 200; r++) {
                vector<int> a = gen(rng, N, hi);
                vector<int> b = a;
                sort(b.begin(), b.end());
                if (adjacent_find(b.begin(), b.end()) != b.end()) dup++;
                if (longestNonIncr(a, true) != longestNonIncr(a)) bad1++;   // 第一问写反
                if (longestIncr(a, true) != longestIncr(a)) bad2++;         // 第二问写反
            }
            out.push_back(bad1); out.push_back(bad2); out.push_back(dup);
            if (!CSV) printf("② n = %d，值域 ≤ %7d（比值 %.3f，200 轮）："
                             "第一问写反被抓 %d，第二问写反被抓 %d，有重复元素 %d\n",
                             N, hi, (double)N / hi, bad1, bad2, dup);
        }
        row("ratio", out);
    }

    /* ③ 题面顶格：鸽巢保证有重复 */
    {
        mt19937 rng(1020u);
        vector<int> a = gen(rng, 100000, 50000);
        vector<int> b = a;
        sort(b.begin(), b.end());
        ll pairs = 0;
        for (size_t i = 1; i < b.size(); i++) if (b[i] == b[i - 1]) pairs++;
        if (!CSV) printf("③ 题面顶格（n = 10^5，高度 ≤ 5×10^4）：n 比值域还大 ⇒ 鸽巢原理保证有重复；"
                         "实测相邻相等的对数 %lld\n", pairs);
        row("pigeon", {100000, 50000, pairs});
    }

    /* ④ 「把第一个数当成 n」的抓获率 */
    {
        mt19937 rng(4444u);
        int rounds = 300, bad = 0;
        for (int r = 0; r < rounds; r++) {
            vector<int> a = gen(rng, (int)(rng() % 20) + 2, 10);
            // 那一版：把 a[0] 当成个数，然后最多再读 a[0] 个（这里数据里数不够就全读）
            vector<int> sub(a.begin() + 1, a.end());
            if (longestNonIncr(sub) != longestNonIncr(a) || longestIncr(sub) != longestIncr(a)) bad++;
        }
        if (!CSV) printf("④ %d 轮：把第一个数当成 n（于是少读了第一发）—— 答案不同 %d 轮\n", rounds, bad);
        row("readn", {rounds, bad});
    }

    /* ⑤ 两问各自的 bound 写反，各自那一问会不会错（题面按问给分） */
    {
        mt19937 rng(555u);
        int rounds = 200, bad1 = 0, bad2 = 0, both = 0;
        for (int r = 0; r < rounds; r++) {
            vector<int> a = gen(rng, 2000, 1000);          // 比值 2.0 —— 和题面顶格一致
            bool w1 = longestNonIncr(a, true) != longestNonIncr(a);
            bool w2 = longestIncr(a, true) != longestIncr(a);
            if (w1) bad1++;
            if (w2) bad2++;
            if (w1 && w2) both++;
        }
        if (!CSV) printf("⑤ %d 轮（n = 2000，值域 1000，比值 2.0 —— 和题面顶格一致）：\n"
                         "   只写反第一问的 bound ⇒ 第一问错 %d 轮；只写反第二问 ⇒ 第二问错 %d 轮；"
                         "两个都写反 ⇒ 两问都错 %d 轮\n"
                         "   ⇒ 题面按问给分，写反一个**只丢一半**\n", rounds, bad1, bad2, both);
        row("perq", {rounds, bad1, bad2, both});
    }
    return 0;
}

// P1020 对拍生成器：`./p1020Gen <seed> [n 上限] [值域上限]`
//   默认 `n ≤ 20`、高度 ≤ 10 —— ⚠ 这两个数不是随手定的。
//
// ★★★ 这一页的旋钮是 **`n / 值域` 的比值**，不是 n 本身
//   （[第 7 章 P1102](/sol/p1102/) 那条「不是『小数据』，是比值」的又一次）：
//   题面顶格是 `n = 10⁵`、高度 ≤ `5 × 10⁴` ⇒ **比值 2.0**（平均每个高度出现两次），
//   而这个默认档 `n ≤ 20`、值域 10 ⇒ **比值也是 2.0**。
//   ⇒ **照抄题面的「比值」，而不是照抄题面的「绝对规模」** ——
//     这样既能用 `2ⁿ` / `O(n²)` 当参照物，又保住了「重复满地都是」这个关键性质。
//
// ⚠ 反例就在同一轮：[B3637](/sol/b3637/) 照题面随机时比值只有 **0.005**，
//   同一类 bug 300 轮只抓到 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]) : 20;
    int vHi = argc > 3 ? atoi(argv[3]) : 10;
    nHi = max(1, min(100000, nHi));
    vHi = max(1, min(50000, vHi));

    mt19937 rng(seed * 2654435761u + 1020u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    for (int i = 0; i < n; i++)
        printf("%u%c", (unsigned)(rng() % (unsigned)vHi) + 1, i + 1 == n ? '\n' : ' ');
    return 0;
}