E – Roadwork 解説（AtCoder Beginner Contest 128）

2020年3月15日2021年12月1日AtCoder更新,データ構造,set,imos法,遅延評価セグメント木,イベントソート,座標圧縮,競プロ,セグメント木,区間

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
$i$ 番目の道路工事は時刻 $S_i−0.5$ から時刻 $T_i−0.5$ まで座標 $X_i$ が通れなくなる。
$j$ 番目の人は時刻 $D_j$ に座標 0 を出発し、速度 1 で正の方向へ歩き続ける。 通行止めとなっている地点に到達した場合には、そこで止まる。
Q 人それぞれが進む距離を求めよ。ただし止まらない場合は -1 を出力する。

制約

• $1 \leq N, Q \leq 2 \times 10^5$
• $0 \leq S_i < T_i \leq 10^9$
• $1 \leq X_i \leq 10^9$
• $0 \leq D_1 < D_2 < … < D_Q \leq 10^9$

考え方

単純にシミュレーションするのは難しそうですし、計算時間も間に合いません。

まずは $i$ 番目の道路工事が $j$ 番目の人に影響を与えるのはどのような場合かを考えてみましょう。

座標 $X_i$ に到達するのは、$D_j + X_i$ になります。全て整数であることに注意すると以下の式が成り立ちます。

つまり区間 $[S_i – X_i, T_i – X_i)$ に $D_j$ があれば、人 $j$ がその通行止めの影響を受ける可能性があります。

• $[S_i – X_i, T_i – X_i)$ に $D_j$ が存在すれば、人物 $j$ は少なくとも $X_i$ で止まる

影響を受ける人は１人とは限らないので以下のように言えるはずです。

• $[S_i – X_i, T_i – X_i)$ に存在する $D_j, D_{j+1}, D_{j+2}, …, D{k}$ に対応する人物 $j, j+1, j+2, …, k$ が少なくとも $X_i$ で止まる

注意としては、より手前側で通行止めがあった場合は、後半の通行止めの影響を受けない点です。つまり、より小さい $X_k$ で同様の条件を満たせば、少なくとも $X_k$ で止まるはずです。

以上からやりたいこととしては、

• 「人物 $j, j+1, j+2, …, k$ が少なくとも $X_i$ で止まる」という区間の更新を N 回上手く行う

ということになります。

解法１：遅延評価セグメント木

想定解法ではありませんが、「区間更新・一点取得」のセグメント木で解くことができます。

区間の更新は遅延評価セグメント木で行うことができます。更新時は値を置き換えるのではなく、$X_i$ の最小値を取るようにしましょう。

人物の番号を、セグメント木の葉に対応させましょう。「人物 $l, l+1, l+2, …, r-1$ が少なくとも $X_i$ で止まる」というのが分かったら、seg.update(l, r, X[i]) などと更新してやればよいです。

どこからどこまでの区間を更新すれば良いかは、二分探索で求めることができます。

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

/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
    set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b):  [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/

template <typename X, typename M>
struct SegTreeLazy {
    using FX = function<X(X, X)>;
    using FA = function<X(X, M)>;
    using FM = function<M(M, M)>;
    int n;
    FX fx;
    FA fa;
    FM fm;
    const X ex;
    const M em;
    vector<X> dat;
    vector<M> lazy;
    SegTreeLazy(int n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
        : n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }

    void set(int i, X x) { dat[i + n - 1] = x; }
    void build() {
        for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
    }

    /* lazy eval */
    void eval(int k) {
        if (lazy[k] == em) return;  // 更新するものが無ければ終了
        if (k < n - 1) {            // 葉でなければ子に伝搬
            lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
            lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
        }
        dat[k] = fa(dat[k], lazy[k]);
        lazy[k] = em;
    }

    void update(int a, int b, M x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {  // 完全に内側の時
            lazy[k] = fm(lazy[k], x);
            eval(k);
        } else if (a < r && l < b) {                     // 一部区間が被る時
            update(a, b, x, k * 2 + 1, l, (l + r) / 2);  // 左の子
            update(a, b, x, k * 2 + 2, (l + r) / 2, r);  // 右の子
            dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    void update(int a, int b, M x) { update(a, b, x, 0, 0, n); }

    X query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) {  // 完全に外側の時
            return ex;
        } else if (a <= l && r <= b) {  // 完全に内側の時
            return dat[k];
        } else {  // 一部区間が被る時
            X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return fx(vl, vr);
        }
    }
    X query(int a, int b) { return query_sub(a, b, 0, 0, n); }

};

int main() {
    // 入力
    int N, Q;
    cin >> N >> Q;
    vector<int> S(N), T(N), X(N);
    for (int i = 0; i < N; i++) {
        cin >> S.at(i) >> T.at(i) >> X.at(i);
    }
    vector<int> D(Q);
    for (int i = 0; i < Q; i++) {
        cin >> D.at(i);
    }

    // 遅延評価セグメント木にのせる作用付きモノイド
    using M = int;
    auto fx = [](int x1, int x2) -> int { return min(x1, x2); };
    auto fa = [](int x, M m) -> int { return min(x, m); };
    auto fm = [](M m1, M m2) -> M { return min(m1, m2); };
    int ex = numeric_limits<int>::max();
    int em = numeric_limits<int>::max();
    SegTreeLazy<int, M> seg(Q, fx, fa, fm, ex, em);

    // セグ木を構築
    for (int i = 0; i < Q; i++) {
        seg.set(i, ex);
    }
    seg.build();

    // 区間更新
    for (int i = 0; i < N; i++) {
        int r = lower_bound(D.begin(), D.end(), T[i] - X[i]) - D.begin();
        int l = lower_bound(D.begin(), D.end(), S[i] - X[i]) - D.begin();
        seg.update(l, r, X[i]);
    }

    // 1点取得
    for (int i = 0; i < Q; i++) {
        int s = seg.query(i, i + 1);
        if (s == ex) {
            cout << -1 << endl;
        } else {
            cout << s << endl;
        }
    }

    return 0;
}

解法２：イベントソート

公式解説にもある方法で、イベントソートと呼ばれる方法で解くこともできます。

イベントを時系列順にソートすることで、「ある時刻 t までにどのイベントが起きて、現在（時刻t）がどんな状態なのか」を時系列順にたどることができます。

今回で言えば２種類のイベントが考えられます。

• 時刻 $S_i – X_i$ からイベント $i$ 開始。以降に出発した人は $X_i$ で通行止め
• 時刻 $T_i – X_i$ にイベント $i$ 終了。以降に出発した人は $X_i$ で通行止めされない

時系列順にたどるので、現在時刻 t の状態として、

• いま発生しているイベントの内容（具体的には $X_i$ の値）

を set などで保持しておく必要があります。イベントの開始には「値の挿入」、イベントの終了には「値の削除」を行えば良いです。

全体のイメージとしては、時間という区間を圧縮した imos 法のような形です。

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

int main() {
    // 入力
    int N, Q;
    cin >> N >> Q;
    vector<int> S(N), T(N), X(N);
    for (int i = 0; i < N; i++) {
        cin >> S.at(i) >> T.at(i) >> X.at(i);
    }
    vector<int> D(Q);
    for (int i = 0; i < Q; i++) {
        cin >> D.at(i);
    }

    // イベント
    vector<tuple<int, int, int>> event;
    for (int i = 0; i < N; i++) {
        event.push_back(make_tuple(S[i] - X[i], 1, X[i]));   // 通行止め開始イベント
        event.push_back(make_tuple(T[i] - X[i], -1, X[i]));  // 通行止め終了イベント
    }
    sort(event.begin(), event.end());  // 時系列順に並べる

    set<int> se;  // 現在出発した人が当たる可能性のある通行止めの情報を保存する set

    vector<int> ans(Q);
    int t = 0;
    int id = 0;
    for (int i = 0; i < Q; i++) {  // 時系列順に見ていく
        t = D[i];
        for (; id < (int)event.size() && get<0>(event[id]) <= t; id++) {
            if (get<1>(event[id]) == 1) {  // イベント開始
                se.insert(get<2>(event[id]));
            } else {  // イベント終了
                se.erase(get<2>(event[id]));
            }
        }
        if (se.empty()) {
            ans[i] = -1;
        } else {
            ans[i] = *se.begin();
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}