【イベントソート】区間更新を遅延セグ木なしでやりたい話

 

この記事でやること

0埋めで初期化された配列に対する以下のようなクエリをオフライン(クエリ先読みができる状態)で処理する方法を考えます:

 

  1.  L \quad R \quad X: \quad 配列の[L, R) をXに更新
  2.  T: \quad 配列のT番目の値を出力

 

遅延セグ木を使えばオンラインで実現できますが、仕組みを理解し実装するのは結構難しいですし、機能的にはオーバーキルです。

 

(以下のサイトは私が遅延セグ木を勉強したときに参考にさせて頂いたものです。気になる方はこちらを参照して頂ければと思います。)

セグメント木を徹底解説!0から遅延評価やモノイドまで | アルゴリズムロジック

 

そこで、イベントソートというテクニックを使って、平衡二分探索木wikipedia)を使えば解ける形に落とし込みます。

 

c++など平衡二分探索木が標準で用意されている言語であればこれで終わりなのですが、私が競プロで使っているPythonには残念ながら用意されていません。

自力で実装するには割と大変なデータ構造で、私もまだ実装したことないんですよね…。

 

載せてあるソースコードでは1行目でBBST(Balanced Binary Search Tree=平衡二分探索木)という名前のclassをimportしていますが、これは、比較的実装しやすいデータ構造であるBIT(Binary Indexed Tree)で同様の機能を再現したもので、本当の平衡二分探索木ではありません。その辺の話は気が向いたらそのうちまた記事を書くと思います。(多分)

 

(BITについて気になる方は下記のサイトを参照してみてください。)

Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで | アルゴリズムロジック

 

実現方法の説明

イベントソートとは?

平面走査を行う上での前準備のことです。

平面走査って何ぞ?という方も、図を見れば雰囲気は掴めるかと思いますのでご安心ください。

 

平面走査による解法

各クエリを、横軸 iが配列のindex、縦軸 jがクエリの番号とした座標平面に図示してみます。

赤色:更新クエリ、青色:回答クエリ

この座標平面を、 iについて昇順に走査します。

 iを時間軸、各クエリを「決まった時間に開始・終了するイベント」と捉え、「進行中の更新イベントの番号」を記録しながら時間を進めていきます。

 i = 1の図。発生中のイベントは \{0, 3\}

 i = 2に到達すると、回答イベント j = 4が発生します。このとき、元の配列の i = 2番目のデータは、進行中の更新イベントのうち j = 4より小さい番号で最大のものを参照すればよいです。

青線について、交わる赤線のうち最も下にあるものを参照する

 

ということは、「進行中のイベントの番号」を平衡二分探索木で記録しておけばよさそうです。正確に書くと、

  1. 更新イベント開始: insert(-j)
  2. 更新イベント終了: erase(-j)
  3. 回答イベント: k = -upper\_bound(-j)として、 X_kを出力*1

とすることで各イベントが O(logQ)処理できます。

 

平面走査のための前準備

実際に上記の平面走査を行うためには、 (イベントの時刻i, イベントの番号j, イベントの種類q \in \{1, 2, 3\})という3つの情報を持ったデータを昇順にソートしておきます。(これをイベントソートと言います。)

 

あとは、尺取り法の要領でイベントを処理していけばよいです。

 

ソースコード

(Python3.8.3)

from BBST_like import BBST

if __name__ == "__main__":
    N, Q = map(int, input().split()) # 配列の長さ、クエリの数
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    # イベントソート
    events = []
    for j in range(Q):
        query = querys[j]
        if len(query) == 3:
            l, r, x = query
            events.append((l, j, 1))
            events.append((r, j, 2))
        else:
            t = query[0]
            events.append((t, j, 3))
    events.sort()

    bbst = BBST(list(range(Q)))
    # 平衡二分探索木のようなもの。引数は気にしなくいいです。
    #「bbst.lt(x): key < x を満たす最大のkeyを取得」という関数を用意してあるので、
    # 解説のように-1倍してupper_boundをする、という実装はしてません。
    
    # 平面走査
    ans = [None]*Q
    e = 0 # eventのindex
    for i in range(N): # iについて昇順に走査
        while e < len(events) and events[e][0] == i: # 発生したイベントを処理
            i, j, q = events[e]
            if q == 1:
                bbst.insert(j)
            elif q == 2:
                bbst.erase(j)
            else:
                k = bbst.lt(j)
                if k is None:
                    ans[j] = 0
                else:
                    ans[j] = querys[k][2]
            e += 1

    for a in ans:
        if a is not None: print(a)

"""
入力例
10 5
1 4 2
2 5 1
3
0 4 3
2

出力
1
3

"""

 

余談:どうせなら区間演算も遅延セグ木なしでやりたい

競プロ典型90問に、遅延セグ木が想定解の問題がありました。

atcoder.jp

 

区間演算の結果を利用して区間更新しろという無茶ぶり。これを遅延セグ木を使わずに解く方法ってあるのでしょうか?

私には思いつかないので、もしわかる方がいらっしゃれば教えていただけると幸いです。

 

追記

rsk0315さんに解説を書いていただきました。ありがとうございます!

atcoder.jp

 

おわりに

遅延セグ木を勉強した方が手っ取り早いのでは?と言われると、それはそう…

でもまあ、イベントソートないし平面走査はとても重要な典型知識だと思うので、頭の片隅にでもいれておきましょう。

逆張りオタクのような内容の記事でしたが、最後までお読みいただきありがとうございました。

*1:upper_bound(x)は「xより大きい最小の値」を求めるので、-1倍して大小関係を反転させています。