Chokudai SpeedRun 002 L問題：長方形 β

問題. 長方形 β

$N$ 個の長方形があり， $i$ 番目の長方形の幅と高さはそれぞれ $A_i, B_i$ である． $N$ 個の長方形の内いくつかを選び軸平行に順番に重ねていく．このとき，前に置かれている長方形の内部で辺に接しないように設置する必要がある．このとき，最大で何個の長方形を重ねることができるかを求めよ．

制約： $1 \le N \le 2 \times 10^5$ ，　 $1 \le A_i, B_i \le 10^9$

解法．最長増加部分列

次の解説を参考にした．

各長方形を頂点として， $i$ 番目と $j$ 番目の長方形に対して， $i$ が $j$ を含むときに弧 $(i, j)$ を加えた有向グラフ $G$ を考える． $G$ は DAG となることが分かるので，DAG 上の最長パス問題に帰着したくなるが， $G$ を陽に構成しようとすると辺集合を求める部分で $O(N^2)$ 時間かかるので時間内に求めることができない．そこで，長方形の包含関係を幾何的に解釈することによって $G$ を陽に求めずに答えを求めることができるかを考える．

弧 $(i, j) \in E(G)$ であるための必要十分条件は， $(A_i \ge A_j \wedge B_i \ge B_j)$ または $(A_i \ge B_j \wedge B_i \ge A_j)$ となることであるが，各長方形を $A_i \ge B_i$ とすることによって， $A_i \ge A_j \wedge B_i \ge B_j$ とすることができる．
ここで，幅に関して昇順に整列をしたときの高さの列を $B' = (B'_1, B'_2, \ldots, B'_N)$ とする．すべての長方形の幅が異なるとすると，重ねることができる最大個数の長方形の置く順番と， $B'$ 上の最長増加部分列が一致することが分かるので，答えは $B'$ の最長増加部分列の長さとなる．
幅が等しい長方形がある場合を考えるが，そのようなどの2つの長方形 $i, j$ に対しても， $(i, j) \notin E(G)$ かつ $(j, i) \notin E(G)$ となる．なぜならば， $A_i = A_j$ かつ $B_i \le B_j$ のとき， $j$ を回転させても $A_i = A_j \ge B_j$ かつ $B_i \le B_j = A_j$ となるからである．したがって，幅に関して昇順に整列したとき，等しい値同士は高さに関して降順に整列することによってお互いを含むことができなくなる．

計算時間： $O(N \log N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

template<typename T>
std::vector<int> longestIncreasingSubsequence(const std::vector<T> &a) {
    if (a.empty()) return {};

    const T INF = std::numeric_limits<T>::max();
    const int size = a.size();

    std::vector<T> dp(size, INF);
    std::vector<int> idx(size);
    for (int i = 0; i < size; ++i) {
        idx[i] = std::distance(dp.begin(), lower_bound(dp.begin(), dp.end(), a[i]));
        dp[idx[i]] = a[i];
    }

    int len = *max_element(idx.begin(), idx.end());
    std::vector<int> lis_idx(len + 1);
    for (int i = size - 1; 0 <= i; --i)
        if (idx[i] == len) lis_idx[len--] = i;

    return lis_idx;
}

void Solve() {
    int n;
    cin >> n;

    vector<pair<int, int>> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i].first >> d[i].second;
        if (d[i].first < d[i].second)
            swap(d[i].first, d[i].second);
        d[i].second *= -1;
    }
    sort(d.begin(), d.end());

    vector<int> a(n);
    for (int i = 0; i < n; ++i) a[i] = -d[i].second;

    auto lis = longestIncreasingSubsequence(a);
    cout << lis.size() << '\n';
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    Solve();

    return 0;
}