LR 法

この呼び方は一般的な用語ではないですが、ある場所でよく使っていたのでここでもそのまま使っています ¹ 。

やりたいこと

$N$ 要素からなる集合 $\lbrace 0,\ \cdots,\ N-1 \rbrace$ がある。このとき次のクエリを処理してください。

• ${\rm delete}(i)$: 要素 $i$ を削除する
• ${\rm left}(i)$: $i$ 未満の要素の中で最大の要素の値（なければ $-1$ ）を返す
• ${\rm right}(i)$: $i$ より大きい要素の中で最小の要素の値（なければ $N$ ）を返す

すでに削除された $i$ が引数として与えられないことが保証されるパターンと与えられる可能性があるパターンがあります。ここでは後者でも対応できるものを想定しています。

平衡二分木

平衡二分木があればすべて処理できます。ややオーバーキルですが、組み込みで平衡二分木がある言語ならそれで十分かもしれません。

実装

データの持ち方

各要素 $i$ に対して、その左隣の要素 ² と右隣の要素 ³ を配列で記録します。本記事では、それぞれ配列 $L$ および $R$ で表します ⁴ 。また $i$ がまだ削除されていないかどうかを表す長さ $N$ の配列 $X$ も用意しておきます。最初はすべての $0\le i\lt N$ について $X[i] = 1$ です。 $i$ が削除されたら $X[i]=0$ になります。

経路圧縮

Union Find の実装と同様に、一度通った経路は圧縮しておくと次からのクエリで同じ部分を再度通らずに処理できます。

コード

Python でのコード例を書いておきます。実際の使い方は「例」の項を参照してください。

test.py

class LR_trick():
    def __init__(self, n):
        self.n = n
        self.L = [i - 1 for i in range(n)]
        self.R = [i + 1 for i in range(n)]
        self.X = [1] * n
    
    def delete(self, i):
        self.X[i] = 0
    
    def left(self, i):
        i = self.L[i]
        li = []
        while i >= 0 and self.X[i] == 0:
            li.append(i)
            i = self.L[i]
        for j in li:
            self.L[j] = i
        return i
        
    def right(self, i):
        i = self.R[i]
        li = []
        while i < self.n and self.X[i] == 0:
            li.append(i)
            i = self.R[i]
        for j in li:
            self.R[j] = i
        return i

計算量

上の実装の場合、構築は $O(N)$ 、削除クエリは $O(1)$ です。
$\rm left,\ right$ クエリは、削除された要素が与えられない場合はならし $O(1)$ です。与えられる可能性がある場合はならし $O(\log N)$ になる気がします。ちゃんと証明していないので違っていたら教えてください。

例（ネタバレ注意）

例 1

ABC 218-H
AC コード

DeletableHeapq と LR 法を使うと実装がラクですね。

1. Dancing Links と呼ばれるものが近そうですが、目的などが少し違いそうな気がします。 ↩

2. それより小さい要素の中で最大のもの ↩

3. それより大きい要素の中で最小のもの ↩

4. LR 法という名前の由来です。 ↩