最长递增子序列（nlogn 二分法、DAG 模型 和 延伸问题）

int lengthOfLIS(vector<int>& nums) {
    vector<int> p{nums[0]};

   for (int i = 1; i < nums.size(); i++) {
       if (auto num = nums[i]; num > p.back())
           p.push_back(num);
       else {
           auto j = lower_bound(p.begin(), p.end(), num);
           *j = num;
       }
   }
   return p.size();
}

for (int i = 1; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j])
            dp[i] = max(dp[i], dp[j] + 1);
    }
    ans = max(ans dp[i]);
}

class Solution {
   public:
    vector<int> findOneLIS(vector<int>& nums) {
        using Node = pair<int, int>;  // 槽位, {父节点在桶中的位置、元素值}
        using Bucket = vector<Node>;  // 桶

        vector<Bucket> buckets;  // 各个列的桶
        vector<int> p;           // 辅助数组, 冗余各个桶的尾部元素

        // 放入头节点到第一个桶
        buckets.push_back({{-1, nums[0]}});
        p.push_back(nums[0]);

        // 辅助函数, 给第 k 个桶放入一个新元素
        auto push = [&](int k, int num) {
            // 上个桶的当前尾部节点当做父节点
            int j = (k == 0) ? -1 : (buckets[k - 1].size() - 1);
            buckets[k].push_back({j, num});
            // 更新辅助数组
            p[k] = num;
        };

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > p[p.size() - 1]) {
                // 新建一个空桶, 扩展辅助数组
                buckets.push_back({});
                p.push_back(0);

                // 加入此元素到新桶 (最后一个桶)
                push(buckets.size() - 1, nums[i]);
            } else {
                // 查找合适的桶放入新元素
                int k = lower_bound(p.begin(), p.end(), nums[i]) - p.begin();
                push(k, nums[i]);
            }
        }

        // 要返回最长的上升子序列，需要从最后一个桶反向找回去
        vector<int> ans(buckets.size());

        // i 是第 i 个桶，j 父节点在前面一个桶的位置
        for (int i = buckets.size() - 1, j = -1; i >= 0; i--) {
            auto& b = buckets[i];
            auto& [j1, num] = b[j < 0 ? (b.size() - 1) : j];
            j = j1;
            ans[i] = num;
        }

        return ans;
    }
};

class Solution {
   public:
    int findNumberOfLIS(vector<int>& nums) {
        // 各个列的桶, 每个桶存放元素的值
        vector<vector<int>> buckets;
        // 每一个桶的二分检索起点, 递进式二分
        vector<int> locs;
        // 前缀和桶， sums[k][j] 表示第 k 个桶上的 [0..j] 区间上的路径计数的总和
        vector<vector<int>> sums;
        // 辅助数组, 快照任一时刻各个桶的尾部元素, 辅助主迭代
        vector<int> p;

        // 放入头节点到第一个桶
        buckets.push_back({nums[0]});
        locs.push_back(0);
        sums.push_back({1});
        p.push_back(nums[0]);

        // 辅助函数, 给第 k 个桶放入一个新元素
        // 并同步计算路径总数, 时间复杂度 log(n)
        auto push = [&](int k, int num) {
            // 找到上一个桶中严格小于 num 的项，然后把计数累加起来
            // 如果是第 0 个桶，count 初始化为 1
            int count = 1;

            if (k >= 1) {
                // 需要注意的是 buckets 数组的尾部才是桶顶
                // buckets[k] 都是递减排列的;
                // 本次 loc 可以作为下次的二分起点
                // 所谓，维护 loc 数组以递进式二分
                int k1 = k - 1;
                auto& b1 = buckets[k1];
                int loc = upper_bound(b1.begin() + locs[k1], b1.end(), num,
                                      greater<int>()) -
                          b1.begin();
                locs[k1] = loc;  // 更新上一个桶的检索节点

                // 前一个桶的区间 [0..loc] 的 count 总和
                // 即区间 [loc, n) 的 (总和 - 前缀和)
                auto total = sums[k1][buckets[k1].size() - 1];

                // 区间  [0.. loc-1] 的计数和::
                // 如果 loc 是 0 , 则相当于区间 [loc, n) 上是求总和
                auto sum_before_loc = loc > 0 ? sums[k1][loc - 1] : 0;
                count = total - sum_before_loc;
            }

            buckets[k].push_back(num);
            p[k] = num;  // 更新辅助数组

            // 更新前缀和
            auto sum = count;
            if (!sums[k].empty()) sum += sums[k][sums[k].size() - 1];
            sums[k].push_back(sum);
        };

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > p[p.size() - 1]) {
                // 扩展桶列表, 扩展辅助数组
                buckets.push_back({});
                sums.push_back({});
                locs.push_back(0);  // 初始化其检索起点 0
                p.push_back(0);
                // 推入此元素到这个新桶
                push(buckets.size() - 1, nums[i]);
            } else {
                // 查找合适的桶放入新元素
                int k = lower_bound(p.begin(), p.end(), nums[i]) - p.begin();
                push(k, nums[i]);
            }
        }

        // 最长上升序列的个数，就是最后一个桶中所有元素的路径数的总和
        const auto& last = sums[sums.size() - 1];
        return last[last.size() - 1];
    }
};

class Solution {
   public:
    int maxEnvelopes(vector<vector<int>>& es) {
        int n = es.size();

        // 先优先按 w 排序
        sort(es.begin(), es.end(), [](const auto& a, const auto& b) {
            // 如果 w 相同，h 则逆序
            // 这里非常巧妙，逆序过来之后，相同的 w 情况下保证 LIS 求解最多取 1 个
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });

        vector<int> p;  // h 升序排列的辅助数组
        p.push_back(es[0][1]);

        for (int i = 1; i < n; i++) {
            auto num = es[i][1];
            if (num > p.back())
                p.push_back(num);
            else {
                auto t = lower_bound(p.begin(), p.end(), num);
                *t = num;
            }
        }

        return p.size();
    }
};

class Solution {
   public:
    // 传统 LIS 问题
    int originalLIS(vector<int>& nums) {
        vector<int> p{nums[0]};

        for (int i = 1; i < nums.size(); i++) {
            if (auto num = nums[i]; num > p.back())
                p.push_back(num);
            else {
                auto j = lower_bound(p.begin(), p.end(), num);
                *j = num;
            }
        }
        return p.size();
    }

    // 非严格递增 LIS 问题
    int looseLIS(vector<int>& nums) {
        // 制作一个下标数组
        vector<int> arr;
        for (int i = 0; i < nums.size(); i++) arr.push_back(i);
        // 按数值排序. 如果数值相等，因为允许非严格递增, 则按下标正序
        sort(arr.begin(), arr.end(), [&](const auto& a, const auto& b) {
            return nums[a] < nums[b] || (nums[a] == nums[b] && a < b);
        });
        // 然后求下标数组的最长严格递增序列
        return originalLIS(arr);
    }
};

class Solution {
   public:
    int LIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        vector<int> p;
        p.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > p.back())
                p.push_back(nums[i]);
            else {
                auto t = lower_bound(p.begin(), p.end(), nums[i]);
                *t = nums[i];
            }
        }
        return p.size();
    }
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        if (m > n) return longestCommonSubsequence(text2, text1);

        // text2 中每个字符在 text2 中出现的所有位置
        unordered_map<char, vector<int>> d;
        for (int i = 0; i < n; i++) d[text2[i]].push_back(i);

        // 制作一个数组
        // 把 text1 中每个字符替换其成在 text2 出现位置的逆序列, 拉平
        vector<int> nums;
        for (auto ch : text1)
            if (d.find(ch) != d.end())
                for (int j = d[ch].size() - 1; j >= 0; j--)
                    nums.push_back(d[ch][j]);

        return LIS(nums);
    }
};

// LIS 问题求解
int LIS(vector<int>& nums) {
    vector<int> p{nums[0]};

    for (int i = 1; i < nums.size(); i++) {
        if (auto num = nums[i]; num > p.back())
            p.push_back(num);
        else {
            auto j = lower_bound(p.begin(), p.end(), num);
            *j = num;
        }
    }
    return p.size();
}

int main(void) {
    // 处理输入
    int n;
    cin >> n;
    getchar();  // '\n'

    int c;  // 当前输入

    // a[i] 记录数字 i-1 的所在的位置
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> c;
        a[c - 1] = i;
    }
    getchar();  // '\n'

    // b[i] 记录输入的数字 k, 对应的 k-1 在 a[i] 中的出现的位置
    vector<int> b(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> c;
        b[i] = a[c - 1];
    }

    getchar();  // '\n'
    // 公共子序列的长度就是 b 的最长上升序列
    cout << LIS(b) << endl;
    return 0;
}