このページでは、データ構造と値の取得とは違い(あちらではデータ構造的にどう取得すればオーダーが落ちるのかを書いてる)クエリ処理の典型的な手法を纏めておく。
イベントソート
クエリ系の多くに一つの軸を中心にさまざまな操作が起こるものが多い。例えば、時間軸を中心にいろいろな事件がある時刻からある時刻まで起きるものなどである。
こういうタイプ(よく見るものだが)の問題の典型手法の一つとして、前から見ていくというのがある。それの実装方法の一つに「イベントソート」というものが挙げられる。ちなみに、このイベントソートという名前は検索してもそうヒットしないので、おそらく広く使われてない。ひろめたい。
こういうタイプ(よく見るものだが)の問題の典型手法の一つとして、前から見ていくというのがある。それの実装方法の一つに「イベントソート」というものが挙げられる。ちなみに、このイベントソートという名前は検索してもそうヒットしないので、おそらく広く使われてない。ひろめたい。
イベントソートでは、クエリをすべてイベントという型の構造体に押し込め(C++では実装上std;;pairやstd;;tupleが常用される)、その中でやりたい優先度順に構造体の中の変数の順番をいじくって、二分木に入れるものである。
つまり、うまくクエリを整列できるような形にして、二分木に入れてデータ構造でのO(log n)の操作たちの恩恵にあずかりたいという発想である。(もちろん、データ構造を利用することは実行時間の節約になるが、あまりにも大きなデータになると空間計算量に問題が生じるので、一長一短である)
メジャーなイベントソートとしては、二分木Aを用意し、Aには前述した整列したイベントを入れて、それを整列した順番に処理していく。そのイベント処理の途中で出てくる求値に必要なデータなどを適宜別のコンテナ、二分木に保存しておく。(例えば、今までの最小値を知りたいとなれば、二分木に入れて、求値のたびに二分木から出せばよい)
例題を見よう
ABC128 E (500)
さきほど言ってた特徴が見事に当てはなるイベントソートの典型問題。ちなみに別解としてセグ木で殴るというのがある。(イベントソート系は結構セグ木でもなんとか行けそうなものが多そう)
この場合、求値クエリごとにO(log n)レベルの速度で今までの工事中である場所の距離の最小値を求めることがキーポイントである。
この場合は、修理のスタートとゴールを別々のイベントとして管理して、前から順にみればよい。(ここではO(n log n)の計算量に)求めた修理中の道路の場所は、もう一つの二分木を用意してそこに入れればよい。(この場合、ここでもO(log n)の計算量になってる)
この場合は、修理のスタートとゴールを別々のイベントとして管理して、前から順にみればよい。(ここではO(n log n)の計算量に)求めた修理中の道路の場所は、もう一つの二分木を用意してそこに入れればよい。(この場合、ここでもO(log n)の計算量になってる)
例えば、
更新イベント、x = 2でt = 4で道を作り始める
ならば、イベントソート二分木(4, 開始, 2)と挿入して、別の修理中だと保存する二分木Bに(2)と入れる。
求値イベント、Q = 0ならば、それまでの二分木Bの中での最小のものを出す。
更新イベント、x = 2でt = 4で道を作り始める
ならば、イベントソート二分木(4, 開始, 2)と挿入して、別の修理中だと保存する二分木Bに(2)と入れる。
求値イベント、Q = 0ならば、それまでの二分木Bの中での最小のものを出す。
というような操作を繰り返せばよい。
