洛谷 P1439 两个排列的最长公共子序列

// P1439 的第一反应：**照 LCS 的定义写 O(n²) DP** —— 对，但这道题上根本开不下
//
// `f[i][j]` = P1 前 i 个和 P2 前 j 个的 LCS 长度，
// `f[i][j] = (a[i] == b[j]) ? f[i-1][j-1] + 1 : max(f[i-1][j], f[i][j-1])`。
//
// ⚠⚠ 题面 `n ≤ 10⁵`：
//   · 时间 `10¹⁰` —— 一秒钟的时限下差四个数量级；
//   · **空间更早爆**：`10⁵ × 10⁵` 个 int = **40 GB**（滚动数组能压到 800 KB，但时间还是 10¹⁰）。
//   ⇒ **这一版在这道题上不是「慢一点」，是连数组都开不出来。**
//
// ★ 但它是这一页最可靠的**参照物**（小 n 上用），因为它是把题意照抄一遍，
//   一点「转成 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<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;

    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = (a[i - 1] == b[j - 1]) ? f[i - 1][j - 1] + 1
                                             : max(f[i - 1][j], f[i][j - 1]);
    cout << f[n][n] << "\n";
    return 0;
}

// P1439 两个排列的最长公共子序列 —— ★ 这一版就能 AC
//
// 题意：给出 1..n 的**两个排列** P1、P2，求它们的最长公共子序列长度（`n ≤ 10⁵`）。
//
// ★ 关键一步：**把 LCS 转成 LIS**。
//   记 `pos[v]` = 数 v 在 P1 里的下标；把 P2 里的每个数换成它的 `pos`，得到序列 b。
//   那么「P1 和 P2 的公共子序列」⇔「b 的上升子序列」：
//     · 一个公共子序列，在 P2 里按顺序出现，在 P1 里的下标也必须递增 ⇒ b 上升；
//     · 反过来，b 的一个上升子序列，对应的那些数在两个排列里都是按顺序出现的。
//   ⇒ 答案 = **b 的最长上升子序列长度**，`O(n log n)`。
//
// ⚠⚠ 这一步**完全依赖「两个都是排列」**：`pos` 要有定义，每个数得只出现一次。
//   题面那句「1, 2, …, n 的两个排列」是**命门**，不是背景（页面第 ⑤ 步把它称了重量）。
//
// ★★★ 而这道题上有一件事很值得注意：转化出来的 b **一定是 0..n-1 的一个排列** ——
//   **没有任何重复元素**。⇒ [第 22 章第 ⑩ 步](/ch/22-lis/)那个「`lower_bound` 还是
//   `upper_bound`」的坑，在这道题上是**结构性的 0**：两种写法答案永远相同。
//   ⇒ 和同一轮的 [B3637](/sol/b3637/)（比值 0.005，300 轮抓 2 次）、
//     [P1020](/sol/p1020/)（比值 2.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<int> pos(n + 1, 0);
    for (int i = 0; i < n; i++) { int v; cin >> v; pos[v] = i; }   // v 在 P1 里的下标

    vector<int> tails;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        int x = pos[v];                                            // 换成下标
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << "\n";
    return 0;
}

// P1439 「错法」：把 `lower_bound` 写成 `upper_bound`
//
// ★★★ 而在这道题上它**根本不是错法** —— 两种写法的答案**永远相同**。
//   原因是结构性的：转化出来的序列 b 是 `pos` 的一个排列，**每个下标只出现一次**，
//   而[第 22 章第 ⑩ 步](/ch/22-lis/)那个判据说得很清楚：
//   **没有重复元素时，严格上升和不下降是同一件事。**
//
// ⇒ 这一份留在这儿，是为了把那个坑的抓获率量成**精确的 0**（页面第 ④ 步），
//   而且这个 0 **是题面保证的，不是数据碰巧** —— 和
//   [B3637](/sol/b3637/)（300 轮抓 2 次）、[P1020](/sol/p1020/)（几乎必抓）凑成三个点。

#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> pos(n + 1, 0);
    for (int i = 0; i < n; i++) { int v; cin >> v; pos[v] = i; }
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        int x = pos[v];
        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;
}

// P1439 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1439Count`      人看的版本
// `./p1439Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 「转成 LIS」≡ 照定义写的 `O(n²)` LCS DP；
//   ② ★★★ 那个「一字之差」的坑在这道题上是**精确的 0** —— 而且是**结构性**的
//      （转化出来的一定是排列，没有重复元素）；
//   ③ ⚠⚠ 而这个 0 **配了自检**：把题面那句「两个排列」放开（允许重复），
//      同一个 `upper_bound` 当场就和 `lower_bound` 不同 ⇒ 这段代码是活的；
//   ④ ★★ 顺手称一称那句约束的重量：不是排列时，「转成 LIS」这一步**整个塌掉**；
//   ⑤ ★ 反过来映射也是对的（LCS 对两个序列是对称的）；
//   ⑥ ★ `O(n²)` LCS 在这道题上是什么概念（时间和**空间**各算一遍）。

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

/** 转成 LIS。loose=true 时用 upper_bound（那个「一字之差」的写法） */
static int byLis(const vector<int>& a, const vector<int>& b, bool loose = false) {
    int n = a.size();
    int mx = 0;
    for (int v : a) mx = max(mx, v);
    for (int v : b) mx = max(mx, v);
    vector<int> pos(mx + 1, -1);
    for (int i = 0; i < n; i++) pos[a[i]] = i;          // ⚠ 有重复时这里只留最后一次
    vector<int> t;
    for (int v : b) {
        if (pos[v] < 0) continue;
        int x = pos[v];
        auto it = loose ? upper_bound(t.begin(), t.end(), x) : lower_bound(t.begin(), t.end(), x);
        if (it == t.end()) t.push_back(x);
        else *it = x;
    }
    return (int)t.size();
}
/** 反过来映射（拿 b 的位置去查 a） */
static int byLisRev(const vector<int>& a, const vector<int>& b) {
    return byLis(b, a, false);
}
/** 参照物：照定义写的 O(n²) LCS */
static int byLcs(const vector<int>& a, const vector<int>& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = (a[i - 1] == b[j - 1]) ? f[i - 1][j - 1] + 1
                                             : max(f[i - 1][j], f[i][j - 1]);
    return f[n][m];
}

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

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

    /* ① 转成 LIS ≡ O(n²) LCS，② 那个坑是精确的 0，⑤ 反过来映射也对 */
    {
        mt19937 rng(20260829u);
        int groups = 0, badLcs = 0, badUpper = 0, badRev = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            vector<int> a, b;
            genPerm(rng, (int)(rng() % 60) + 1, a, b);
            int ok = byLis(a, b);
            if (byLcs(a, b) != ok) badLcs++;
            if (byLis(a, b, true) != ok) badUpper++;
            if (byLisRev(a, b) != ok) badRev++;
        }
        if (!CSV) printf("① %d 组（两个排列，n ≤ 60）：转成 LIS vs O(n²) LCS 不一致 %d 组\n"
                         "② 那个「一字之差」的坑（upper_bound）：不同 %d 组 —— **精确的 0**\n"
                         "⑤ 反过来映射：不同 %d 组（LCS 对两个序列是对称的）\n",
                         groups, badLcs, badUpper, badRev);
        row("perm", {groups, badLcs, badUpper, badRev});
    }

    /* ③ ⚠⚠ 自检：把那个 0 造回来 —— 放开「都是排列」，upper_bound 当场就不同了 */
    {
        mt19937 rng(1439u);
        int rounds = 300, diffUpper = 0, badTrans = 0;
        for (int r = 0; r < rounds; r++) {
            vector<int> a, b;
            genDup(rng, (int)(rng() % 40) + 2, a, b);          // ← 违反题面：允许重复
            if (byLis(a, b, true) != byLis(a, b)) diffUpper++;
            if (byLis(a, b) != byLcs(a, b)) badTrans++;        // ④ 转化本身塌了没有
        }
        if (!CSV) printf("③ ⚠ 自检（放开「都是排列」，%d 轮）：upper_bound 和 lower_bound 不同 %d 轮\n"
                         "   ⇒ 上面那个 0 不是空壳，是**题面保证**出来的\n"
                         "④ 同一档：「转成 LIS」和真正的 LCS 不同 %d 轮 —— "
                         "**不是排列，这个转化整个塌掉**\n", rounds, diffUpper, badTrans);
        row("selfcheck", {rounds, diffUpper, badTrans});
    }

    /* ⑥ O(n²) LCS 在这道题上是什么概念 */
    {
        ll n = 100000;
        ll ops = n * n;                                    // 10^10
        ll bytesFull = n * n * 4;                          // int 表
        ll gb = bytesFull / 1024 / 1024 / 1024;
        ll rollingKB = 2 * (n + 1) * 4 / 1024;             // 滚动数组
        if (!CSV) printf("⑥ 顶格 n = 10^5：O(n²) LCS 要算 %lld 次（10^10 量级），"
                         "整表 %lld GB；就算滚动成两行也只有 %lld KB —— **时间那一关还是过不去**\n",
                         ops, gb, rollingKB);
        row("scale", {ops, gb, rollingKB});
    }
    return 0;
}

// P1439 对拍生成器：`./p1439Gen <seed> [n 上限] [是否允许重复]`
//   默认 `n ≤ 60`、**严格照题面造两个排列**。
//
// ★ 第三个参数（默认 0）是给页面第 ⑤ 步用的**违反题面**的一档：
//   传 1 时不再造排列，而是随机造两个可能有重复的序列 ——
//   用来称一称题面那句「1, 2, …, n 的两个**排列**」的重量
//   （⇒ 一旦不是排列，「把 LCS 转成 LIS」这一步整个塌掉）。
//
// ⚠ 默认 n 压在 60，是因为参照物是 `O(n²)` 的 LCS DP（它要开 n² 的表）。

#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]) : 60;
    int dup = argc > 3 ? atoi(argv[3]) : 0;
    nHi = max(1, min(2000, nHi));

    mt19937 rng(seed * 2654435761u + 1439u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    printf("%d\n", n);
    if (!dup) {
        vector<int> a(n), b(n);
        iota(a.begin(), a.end(), 1);
        iota(b.begin(), b.end(), 1);
        shuffle(a.begin(), a.end(), rng);
        shuffle(b.begin(), b.end(), rng);
        for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
        for (int i = 0; i < n; i++) printf("%d%c", b[i], i + 1 == n ? '\n' : ' ');
    } else {
        for (int t = 0; t < 2; t++)
            for (int i = 0; i < n; i++)
                printf("%u%c", (unsigned)(rng() % (unsigned)n) + 1, i + 1 == n ? '\n' : ' ');
    }
    return 0;
}