全順序集合に対するimos法の拡張

AtCoder Beginner Contest 128のE - Roadworkで、imos法を拡張したアルゴリズムを思いついたのでメモ。

前提

「E - Roadwork」は座標圧縮などを使うと次の問題に帰着できる。

以下が与えられる：
- 最大元 $\text{INF}$ をもつ全順序集合 $(X, \leq)$
- 自然数 $M$ と集合 $I := \{0, 1, \ldots, M-1\}$
$\text{INF}$ で埋められた長さ $M$ の配列 $R$ を用意する。
個の次のクエリを処理する：
- $^\forall c \in \lbrack l_i, r_i)$ に対して $R\lbrack c\rbrack \leftarrow \min(R \lbrack c \rbrack , x_i)$ の更新をする。
個の次のクエリを処理する：
- 現在の $R \lbrack q_i \rbrack$ の値を出力する。

制約が「 $\leq 10^5$ 」だと間に合わないので $O(\ast \log \ast)$ に落としたい。

vector<X>（ $X$ 上の動的配列）*1を要素にもつ大きさ $M$ の配列を２つ用意する。これを配列 $U_\text{insert}, U_\text{remove}$ とする。
個のクエリに対して次のように処理する：
1. $U_\text{insert}\lbrack l_i \rbrack.\text{push}(x_i)$
2. $U_\text{remove}\lbrack r_i \rbrack.\text{push}(x_i)$
上の重複要素を許す平衡二分探索木を用意する。具体的には次のメソッドがある：
- $\text{insert}(x)$ ： $O(\log n)$ で $x$ を挿入する。すでに $x$ が入っている場合も重複して挿入する。
- $\text{remove}(x)$ ： $O(\log n)$ で $x$ を１つ削除する。
- $\text{min}()$ ：もっている要素のうち最小の値を $O(1)$ で返す。空のときは $\text{INF}$ を返す。
1. 1. $T.\text{insert}(x)$
2. 1. $T.\text{remove}(x)$
3. $R\lbrack i \rbrack \leftarrow T.\text{min}()$
個の次のクエリに対して次のように処理する：
1. $R\lbrack q_i \rbrack$ を出力する。