# ARC159-D LIS 2

2056diff
https://atcoder.jp/contests/arc159/tasks/arc159_d

## 解法

$i$番目の共通区間を部分列に含めるとき、$R_{i}$まで採用してしまっても損をしない。

このことを踏まえて動的計画法を設計する。

**定義**
$\text{dp}[i] :=$ $i$番目までの区間を考慮したときのLISの長さの最大。

**テーブルの大きさ**
$N$

**初期値**
$\text{dp}[i] =
\begin{cases}
0 & i = 0 \\
-\infty & \text{else} \\
\end{cases}$

**遷移**
$j = 0, 1, 2, \dots, i - 1$について
- $R_{j}\ge R_{i}$なら貰えない
- $R_{j}\lt L_{i}$なら$\text{dp}[j] + R_{i} - L_{i} + 1$貰える
- それ以外は$\text{dp}[j] + R_{i} - R_{j}$貰える

これを愚直にやると$\Theta(N^2)$かかる。そこでLISのdpをセグ木で高速化するのと同じ様なアイデアでこのdpを高速化できないか考える。

$(0, \text{dp}[0]), (R_{1}, \text{dp}[1]), (R_{2}, \text{dp}[2]), \dots, (R_{i - 1}, \text{dp}[i - 1])$からなる$i$個の点が座標平面上にあるとする。$x$座標が$k$である点の中での最大の$y$座標を$Y_{k}$と呼ぶことにする。点が無いなら$Y_{k} = -\infty$とする。$Y$を用いて$\text{dp}[i]$の計算は以下のように言い換えられる。

> $\text{dp}[i] = R_{i} - L_{i} + 1 + \max\{ Y_{0}, Y_{1}, \dots, Y_{L_{i} - 1}, Y_{L_{i}} - 1, Y_{L_{i} + 1} - 2, \dots, Y_{R_{i} - 1} - R_{i} - L_{i}\}$

$\max\{Y_{0}, Y_{1}, \dots, Y_{L_{i} - 1}\}$と$\max\{Y_{L_{i}} - 1, Y_{L_{i} + 1} - 2, \dots, Y_{R_{i} - 1} - R_{i} - L_{i}\}$を別々に計算してやれば良い。前者はそのまま区間max、後者は$x$座標-$y$座標の区間maxを取れば計算できる。

$Y_{k} \ne -\infty$となる$k$は高々$N$個である。そのような$k$のみを考慮するようにすれば(=$R$で座圧せよ)、以上をセグメント木で効率的に計算できるようになる。全体の時間計算量は$\Theta(N\log N)$と見積もれる。

## 実装

#include <bits/stdc++.h>

template <class S>
struct SegmentTree {
    using T = typename S::T;
    int n;
    std::vector<T> data;
    SegmentTree(int N) : n{N}, data(2 * n, S::identity()) {}
    void update(int i, const T& v) {
        assert(0 <= i and i < n);
        data[n + i] = S::operation(data[n + i], v);
        for (int j{(n + i) >> 1} ; j ; j >>= 1) {
            data[j] = S::operation(data[j << 1 | 0], data[j << 1 | 1]);
        }
    }
    T prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        T L{S::identity()}, R{S::identity()};
        for (l += n, r += n ; l < r ; l >>= 1, r >>= 1) {
            if (l & 1) {
                L = S::operation(L, data[l]);
                l++;
            }
            if (r & 1) {
                r--;
                R = S::operation(data[r], R);
            }
        }
        return S::operation(L, R);
    }
};

const long long INF{(long long)-2e9};

struct MAX {
    using T = long long;
    static T identity() { return INF; }
    static T operation(T l, T r) { return std::max(l, r); }
};

struct MAX2 {
    using T = std::pair<long long, int>;
    static T identity() { return { INF, -1 }; }
    static T operation(T l, T r) { return l.first - l.second < r.first - r.second ? r : l; }
};


int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    std::cin >> N;
    std::vector<int> L(N), R(N);
    for (int i{} ; i < N ; i++) {
        std::cin >> L[i] >> R[i];
    }
    std::vector<int> comp{R};
    comp.push_back(0);
    std::sort(comp.begin(), comp.end());
    comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
    assert(comp[0] == 0);
    SegmentTree<MAX> seg(comp.size());
    SegmentTree<MAX2> teg(comp.size());
    seg.update(0, 0);
    teg.update(0, { 0, 0 });
    for (int i{} ; i < N ; i++) {
        auto l{std::lower_bound(comp.begin(), comp.end(), L[i]) - comp.begin()};
        auto r{std::lower_bound(comp.begin(), comp.end(), R[i]) - comp.begin()};
        auto v1{seg.prod(0, l)};
        auto v2{teg.prod(l, r)};
        assert(v2 == MAX2::identity() or (L[i] <= v2.second and v2.second < R[i]));
        long long val{std::max(v1 + R[i] - L[i] + 1, v2.first + R[i] - v2.second )};
        seg.update(r, val);
        teg.update(r, { val, R[i] });
    }
    std::cout << seg.prod(0, comp.size()) << '\n';
}

[提出](https://atcoder.jp/contests/arc159/submissions/58329331)

## 感想

かなり取り組みやすかった。

セグ木のソラ書きを失敗して一箇所バグらせた。船降ります。