この記事でやること
0埋めで初期化された配列に対する以下のようなクエリをオフライン(クエリ先読みができる状態)で処理する方法を考えます:
遅延セグ木を使えばオンラインで実現できますが、仕組みを理解し実装するのは結構難しいですし、機能的にはオーバーキルです。
(以下のサイトは私が遅延セグ木を勉強したときに参考にさせて頂いたものです。気になる方はこちらを参照して頂ければと思います。)
セグメント木を徹底解説!0から遅延評価やモノイドまで | アルゴリズムロジック
そこで、イベントソートというテクニックを使って、平衡二分探索木(wikipedia)を使えば解ける形に落とし込みます。
c++など平衡二分探索木が標準で用意されている言語であればこれで終わりなのですが、私が競プロで使っているPythonには残念ながら用意されていません。
自力で実装するには割と大変なデータ構造で、私もまだ実装したことないんですよね…。
載せてあるソースコードでは1行目でBBST(Balanced Binary Search Tree=平衡二分探索木)という名前のclassをimportしていますが、これは、比較的実装しやすいデータ構造であるBIT(Binary Indexed Tree)で同様の機能を再現したもので、本当の平衡二分探索木ではありません。その辺の話は気が向いたらそのうちまた記事を書くと思います。(多分)
(BITについて気になる方は下記のサイトを参照してみてください。)
Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで | アルゴリズムロジック
実現方法の説明
イベントソートとは?
平面走査を行う上での前準備のことです。
平面走査って何ぞ?という方も、図を見れば雰囲気は掴めるかと思いますのでご安心ください。
平面走査による解法
各クエリを、横軸が配列のindex、縦軸がクエリの番号とした座標平面に図示してみます。
この座標平面を、について昇順に走査します。
を時間軸、各クエリを「決まった時間に開始・終了するイベント」と捉え、「進行中の更新イベントの番号」を記録しながら時間を進めていきます。
に到達すると、回答イベントが発生します。このとき、元の配列の番目のデータは、進行中の更新イベントのうちより小さい番号で最大のものを参照すればよいです。
ということは、「進行中のイベントの番号」を平衡二分探索木で記録しておけばよさそうです。正確に書くと、
- 更新イベント開始:
- 更新イベント終了:
- 回答イベント:として、を出力*1
とすることで各イベントが処理できます。
平面走査のための前準備
実際に上記の平面走査を行うためには、という3つの情報を持ったデータを昇順にソートしておきます。(これをイベントソートと言います。)
あとは、尺取り法の要領でイベントを処理していけばよいです。
ソースコード
(Python3.8.3)
余談:どうせなら区間演算も遅延セグ木なしでやりたい
競プロ典型90問に、遅延セグ木が想定解の問題がありました。
区間演算の結果を利用して区間更新しろという無茶ぶり。これを遅延セグ木を使わずに解く方法ってあるのでしょうか?
私には思いつかないので、もしわかる方がいらっしゃれば教えていただけると幸いです。
追記
rsk0315さんに解説を書いていただきました。ありがとうございます!
おわりに
遅延セグ木を勉強した方が手っ取り早いのでは?と言われると、それはそう…
でもまあ、イベントソートないし平面走査はとても重要な典型知識だと思うので、頭の片隅にでもいれておきましょう。
逆張りオタクのような内容の記事でしたが、最後までお読みいただきありがとうございました。
*1:upper_bound(x)は「xより大きい最小の値」を求めるので、-1倍して大小関係を反転させています。