Travel Agency [第五回 アルゴリズム実技検定 N]

https://atcoder.jp/contests/past202012-open/tasks/past202012_n

解説

https://atcoder.jp/contests/past202012-open/submissions/22304844

クエリ先読みをして解く。
特定のクエリ問題では、クエリを一度にまとめて計算することで計算量の改善を図るものがある。
一部のバッチ処理で用いられているテクニックであるが、今回の問題にも適用できる。

まずは1クエリで考える

考え始めとして、1クエリでの解き方を考えてみよう。
普通にB[i]から左右に移動可能な範囲を伸ばして、訪れることができる範囲を求めればいい。
まず、ここで「訪れることができる範囲はB[i]を含む、ある区間になる」ことに気が付く。
このままの解法では間に合わないが、範囲はある区間になるので、左端と右端が素早く求まれば、
答えも素早く求めることができそうである。
左端と右端を高速に持ってくるすべはないだろうか。

使えない道路を保持する

使えない道路を保持したsetを用意しておく。
かなり唐突だが、知っているやり方を色々思い出すと、このやり方にたどり着く。
他のデータ構造でも問題ない。
使えない道路を保持しておいて、B[i]から左右に一番近い道路を検索する。
この検索にはlower_boundを利用すると高速に検索が可能である。
例えばすべての道路が使える場合など、空っぽになると例外処理を入れる必要があって少し面倒なので、
番兵と呼ばれるダミーデータを入れておくといい。
自分の実装では-1とN-1と番兵としていれている。
これで、「使えない道路を保持したデータ構造が用意されていれば」高速にクエリをさばける状態となった。

クエリ先読み

ここでクエリ先読みを利用する。
クエリ先読みをすることで使用される年齢がすべて分かるので、年齢が小さい順に色々処理をしていくことにする。
処理したいのは以下の3つである。

• 年齢L[i]になったら道路iを有効にする（使えない道路を保持するデータ構造から消す）
• 年齢R[i] + 1になったら、道路iを無効にする（使えない道路を保持するデータ構造に追加する）
• 年齢A[i]になったら、クエリを計算する

この操作を年齢が小さい順に行っていけば、クエリを計算する段階では、使えない道路を保持するデータ構造が
使用したい年齢にあった状態になっている。
年齢A[i]を操作する場合には、それより前の操作は実行されているので、使える道路の状況も期待にあったものに
なっているという感じである。

このようなやり方はクエリ先読みというよりかはクエリ先読みをすることで平面走査ができるようになったと
考える方が正しいかもしれないが、テクニック名というより雰囲気をつかんでほしい。
雰囲気が分かっていれば、実装はそれほど難しくない。

int N, Q, L[201010], R[201010], A[201010], B[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N - 1)cin >> L[i] >> R[i];
    rep(i, 0, Q) cin >> A[i] >> B[i], B[i]--;

    map<int, map<int, vector<int>>> que;
    rep(i, 0, N - 1) {
        que[L[i]][0].push_back(i);
        que[R[i] + 1][1].push_back(i);
    }
    rep(i, 0, Q) que[A[i]][2].push_back(i);

    set<int> ng;
    ng.insert(-1);
    rep(i, 0, N - 1) ng.insert(i);
    ng.insert(N - 1);

    fore(q, que) {
        int age = q.first;
        fore(i, q.second[0]) ng.erase(i);
        fore(i, q.second[1]) ng.insert(i);

        fore(i, q.second[2]) {
            auto ite = ng.lower_bound(B[i]);
            ite--;
            int L = *ite + 1;

            ite = ng.lower_bound(B[i]);
            int R = *ite;

            ans[i] = R - L + 1;
        }
    }

    rep(i, 0, Q) printf("%d\n", ans[i]);
}