洛谷 B3637 最长上升子序列

// B3637 最长上升子序列 —— ★ 这一版就能 AC（O(n log n)）
//
// 这是[第 22 章](/ch/22-lis/)的模板题，正解正文第 ⑥ 步已经讲透了：
//   维护一个 `tails` 数组，`tails[k]` = 所有长度为 k+1 的上升子序列里**最小的那个结尾**。
//   来一个新数 x：在 tails 里找**第一个 ≥ x 的位置**（`lower_bound`），
//   找到就把它替换掉，找不到（x 比所有的都大）就 push_back。
//   ⇒ `tails` 的**长度**就是答案。
//
// ⚠⚠ **`tails` 里存的不是那个最长上升子序列本身**（正文第 ⑧ 步专门说过这件事）——
//   它只是「每个长度的最优结尾」，中途的内容常常是一串不连贯的数。**只有长度是可信的。**
//
// ★ 题面要的是**严格上升**（「逐渐增大」），所以这里是 `lower_bound`。
//   要是题目说「不下降」，就得换成 `upper_bound` —— 一个字母的差别，
//   而它**只有在序列里有相等的数时才会现形**（页面第 ④ 步把这条量成了两层触发条件）。
//
// 复杂度 `O(n log n)`。★ 而题面 `n ≤ 5000` —— `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<int> tails;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto it = lower_bound(tails.begin(), tails.end(), x);   // ★ 严格上升 ⇒ lower_bound
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
    return 0;
}

// B3637 的另一版正解：`O(n²)` 的经典 DP —— ★ 这一版**在这道题上也能 AC**
//
// `f[i]` = 以第 i 个数结尾的最长上升子序列长度；`f[i] = max(f[j]) + 1`（j < i 且 a[j] < a[i]）。
//
// ★ 题单里给这道题写了一句：「先交 `O(n²)` 再交 `O(n log n)`，**对比一下用时**」——
//   页面第 ③ 步把这句话量了出来：题面顶格 `n = 5000` 时它只要几毫秒，
//   ⚠ 而**真正的分界线不在这道题上** —— 要 n 大到 10⁵ 才轮得到 `O(n log n)` 出场
//   （[P1020 导弹拦截](/sol/p1020/)就是那样一道题）。
//
// ⇒ 「哪一版该交」不是「哪一版更优」，是**题面的 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<int> a(n), f(n, 1);
    for (int& x : a) cin >> x;

    int ans = 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);        // ★ 严格上升 ⇒ 这里是 <
        ans = max(ans, f[i]);
    }
    cout << (n ? ans : 0) << "\n";
    return 0;
}

// B3637 的参照物：`2ⁿ` 枚举子集
//
// ★ 它把「最长上升子序列」这句话照抄一遍：枚举每个子集，检查是不是严格递增，取最长的。
//   不需要「状态 / 转移」，也不需要 `tails` 那个巧办法 —— 这正是它当参照物的价值。
// ⚠ 只跑得动 `n ≤ 22` 左右。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int last = INT_MIN, len = 0;
        bool ok = true;
        for (int i = 0; i < n && ok; i++)
            if (mask >> i & 1) {
                if (a[i] <= last) ok = false;                   // ★ 严格上升
                else { last = a[i]; len++; }
            }
        if (ok) best = max(best, len);
    }
    cout << best << "\n";
    return 0;
}

// B3637 错法：把 `lower_bound` 写成 `upper_bound`
//
// 一个字母的差别 —— 它求的是「**最长不下降**子序列」，而题面要的是**严格上升**。
//
// ★★ 而这个 bug 有**两层**触发条件（页面第 ④ 步量了）：
//   ① 序列里**得有相等的数**（没有重复元素时两种写法答案完全一样 —— 正文第 ⑩ 步说过）；
//   ② 那些相等的数还得**真的落在最优解的路上**。
//   ⇒ 照题面随机（`n ≤ 5000`、值 ≤ 10⁶）时第 ① 层几乎必然成立，第 ② 层却很少成立；
//     把值域压到几十，两层就一起成立了。

#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> tails;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto it = upper_bound(tails.begin(), tails.end(), x);   // ← 这里
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
    return 0;
}

// B3637 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./b3637Count`      人看的版本
// `./b3637Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★ 三条路一致：tails 版 / `O(n²)` DP / `2ⁿ` 枚举子集；
//   ② ★★★ 「`lower_bound` 写成 `upper_bound`」那个 bug 的**两层**触发条件 ——
//      「序列里有相等的数」和「真被抓」差多少（拧值域）；
//   ③ ★★ 题单说「先交 `O(n²)` 再交 `O(n log n)`，对比一下用时」—— 量出来，
//      并且指出**这道题上分不出高下**，真正的分界线在别的题上；
//   ④ ★ `tails` 数组**不是**那个最长上升子序列本身 —— 举一个具体的反例。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
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 + lower_bound（严格上升）。cnt 记比较次数 */
static int lisStrict(const vector<int>& a, ll* cnt = nullptr) {
    vector<int> t;
    for (int x : a) {
        auto it = lower_bound(t.begin(), t.end(), x);
        if (cnt) *cnt += (ll)(t.empty() ? 1 : 1 + (ll)(64 - __builtin_clzll(t.size())));
        if (it == t.end()) t.push_back(x);
        else *it = x;
    }
    return (int)t.size();
}
/** 错法：upper_bound（不下降） */
static int lisNonDec(const vector<int>& a) {
    vector<int> t;
    for (int x : a) {
        auto it = upper_bound(t.begin(), t.end(), x);
        if (it == t.end()) t.push_back(x);
        else *it = x;
    }
    return (int)t.size();
}
/** O(n^2) DP（严格上升）。cnt 记内层比较次数 */
static int lisN2(const vector<int>& a, ll* cnt = nullptr) {
    int n = a.size(), ans = 0;
    vector<int> f(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (cnt) (*cnt)++;
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
        ans = max(ans, f[i]);
    }
    return n ? ans : 0;
}
/** 2^n 枚举子集 */
static int lisBrute(const vector<int>& a) {
    int n = a.size(), best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int last = INT_MIN, len = 0;
        bool ok = true;
        for (int i = 0; i < n && ok; i++)
            if (mask >> i & 1) {
                if (a[i] <= last) ok = false;
                else { last = a[i]; len++; }
            }
        if (ok) best = max(best, len);
    }
    return best;
}
static bool hasDup(vector<int> a) {
    sort(a.begin(), a.end());
    return adjacent_find(a.begin(), a.end()) != a.end();
}
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, badBrute = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            vector<int> a = gen(rng, (int)(rng() % 14) + 1, 1000000);
            int ok = lisStrict(a);
            if (lisN2(a) != ok) badN2++;
            if (lisBrute(a) != ok) badBrute++;
        }
        if (!CSV) printf("① %d 组（n ≤ 14）：tails 版 vs O(n²) 不一致 %d 组；vs 2^n 暴力不一致 %d 组\n",
                         groups, badN2, badBrute);
        row("three", {groups, badN2, badBrute});
    }

    /* ② ★★★ 两层触发条件：有重复 vs 真被抓 */
    {
        const int HIS[] = {4, 40, 1000, 1000000};
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 7919u + 37u);
            int dup = 0, caught = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> a = gen(rng, 5000, hi);          // ★ n 照题面顶格
                if (hasDup(a)) dup++;
                if (lisNonDec(a) != lisStrict(a)) caught++;
            }
            out.push_back(dup); out.push_back(caught);
            if (!CSV) printf("② n = 5000，值域 ≤ %7d（300 轮）：有重复元素 %d 轮，"
                             "而 upper_bound 那版真被抓 %d 轮\n", hi, dup, caught);
        }
        row("layers", out);
    }

    /* ③ O(n²) vs O(n log n)：题面顶格分不出高下，真正的线在别处 */
    {
        const int NS[] = {5000, 20000, 100000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 40503u + 7u);
            vector<int> a = gen(rng, n, 1000000);
            ll c1 = 0, c2 = 0;
            auto t0 = steady_clock::now();
            int r1 = lisN2(a, &c1);
            ll ms1 = duration_cast<milliseconds>(steady_clock::now() - t0).count();
            t0 = steady_clock::now();
            int r2 = lisStrict(a, &c2);
            ll ms2 = duration_cast<milliseconds>(steady_clock::now() - t0).count();
            out.push_back(ms1); out.push_back(ms2); out.push_back(r1 == r2 ? 1 : 0);
            if (!CSV) printf("③ n = %6d：O(n²) %5lld 毫秒（内层比较 %lld 次），"
                             "O(n log n) %4lld 毫秒（约 %lld 次），答案%s\n",
                             n, ms1, c1, ms2, c2, r1 == r2 ? "相同" : "**不同**");
        }
        row("timing", out);
    }

    /* ④ tails 不是 LIS 本身 */
    {
        vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
        vector<int> t;
        for (int x : a) {
            auto it = lower_bound(t.begin(), t.end(), x);
            if (it == t.end()) t.push_back(x);
            else *it = x;
        }
        if (!CSV) {
            printf("④ 序列 3 1 4 1 5 9 2 6：最长上升子序列长度 %d，而 tails 里最后剩的是", (int)t.size());
            for (int x : t) printf(" %d", x);
            printf("（★ 它本身**不是**一个上升子序列的原样 —— 只有长度可信）\n");
        }
        vector<ll> o = {(ll)t.size()};
        for (int x : t) o.push_back(x);
        row("tails", o);
    }
    return 0;
}

// B3637 对拍生成器：`./b3637Gen <seed> [n 上限] [值域上限]`
//   默认 `n ≤ 16`、值 ≤ 10⁶ —— n 压在 16 是为了让 `2ⁿ` 暴力当得了参照物，
//   **而值域照题面顶格**（题面：`n ≤ 5000`，数 ≤ 10⁶）。
//
// ★★ 这一页要拧的旋钮是**值域**，而不是 n：
//   「`lower_bound` 写成 `upper_bound`」那个 bug 的第一层触发条件是「序列里有相等的数」，
//   而值域一大就几乎没有重复 —— 这正是正文第 ⑩ 步把生成器值域压到 `1~4` 的原因。
//   ⚠ 而这一页量出来的是：**第一层成立远远不等于被抓**（页面第 ④ 步那张表）。

#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]) : 16;
    int vHi = argc > 3 ? atoi(argv[3]) : 1000000;
    nHi = max(1, min(5000, nHi));
    vHi = max(1, min(1000000, vHi));

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