準備

高橋くんの移動の方法は公式解説と同じです。\(s_{x, i} < t_{x,i}\) を仮定します。

クエリに対して、(現在の位置, 現在の距離) というペアを考えます。あらかじめクエリを全て読み込み、 \(k=1,2, \cdots, N\) の順に、各クエリに対して次のように処理します。

• \(k = s_{x, i}\) なら、ペア \((s_{y,i}, 0)\) を置く
• \(s_{x, i} \lt k \le t_{x, i}\) なら、現在のペアを \((p, d)\) として、次のように処理する
  • \(p < L_i\) なら、ペアを \((L_i, d+L_i-p)\) に更新する
  • \(L_i \le p \le R_i\) なら、何もしない
  • \(R_i < p\) なら、ペアを \((R_i, d+p-R_i)\) に更新する
• \(k = t_{x, i}\) なら、現在のペアを \((p, d)\) として、 クエリに対する答えは \(d+t_{x,i} - s_{x,i}+|t_{y,i} - p|\) である（\(t_{x,i} - s_{x,i}\) は \(x\) 座標の移動、 \(|t_{y,i} - p|\) は最後に行う \(y\) 座標の移動を表す）

このアルゴリズムを使うと、時間計算量 \(O(NQ)\) になります。これでは間に合いません。

高速化

(現在の位置, 現在の距離) というペアに対して、次の性質が成り立ちます： \(1\) ステップ先の位置は、現在の位置だけに依存する。つまり、 \(2\) つのペアがあり、それぞれの「現在の位置」が同じなら、\(1\) ステップ先のそれぞれの「現在の位置」も同じである。さらにその先もずっと同じである。

したがって、現在の位置が同じであるクエリをまとめて処理することを考えます。位置 \(p\) でクエリをまとめ、「現在の位置が \(p\) であるクエリの (クエリの番号、現在の距離) の組の集合」を持つことにします。

集合のマージは、いわゆる「データ構造をマージする一般的なテク（マージテク）」を用いると、全体で高速に行うことができます。

「現在の距離」の更新の問題

しかし、まだ高速化は出来ていません。それは、各クエリの「現在の距離」の更新をクエリごとに行う必要があるからです。そこで、「現在の距離」の更新の差分が位置 \(p\) だけに依存することに注目して、位置 \(p\) の集合ごとにまとめて「現在の距離」を更新することを考えます。

各位置 \(p\) の集合ごとに「現在の距離のオフセット」という数値を持ち、「現在の距離」を更新する際は代わりに「現在の距離のオフセット」を更新することにします。そうすると、集合内のすべてのクエリに対して「現在の距離」を \(O(1)\) 時間で更新できます。

「現在の距離のオフセット」が更新されるタイミングは、現在の位置 \(p\) が \(p < L_i\) または \(p > R_i\) のときです。これは現在の位置が更新されるタイミングでもあります。この更新は全体で \(O(Q+N)\) 回しか起こらないことが分かります。 したがって、ここは高速です。そして、マージテクは「現在の距離のオフセット」を含めて適用することができます。

以上から、合計で時間計算量 \(O((Q+N) \log^2 Q)\)、空間計算量 \(O(Q+N)\) でこの問題が解けました。

shobonvipの解答 (C++, 746ms)