Fully Retroactive Deque

個人的メモ

例えば初めに追加された要素の基準座標を $0$ とする. 以降 push_front, push_back によって追加された要素の座標ををそれぞれ (先頭要素の座標) -1, (末尾要素の座標) + 1 とする. このとき時刻 $time$ における先頭要素の値を求めることを考える. 時刻 $time$ における先頭要素の座標を $pos$ としたときこの要素は "時刻 $\min$ ($time$ より前で初めて先頭要素の座標が $pos + 1$ であった時刻, $time$ より前で初めて末尾要素の座標が $pos - 1$ であった時刻)" の次に行われた push_front もしくは push_back の操作によって追加された要素である. よって先頭要素, 末尾要素それぞれに対して更新操作(push, pop_front, push, pop_back) を時刻をキーとした平衡二分木で保持し, また各ノードについてそれ以下のノードで取りうる先頭要素, 末尾要素の座標の最大値, 最小値などを保持することで $\O( \log n)$ 時間で先頭要素の追加があった時刻を求めることが可能になる. その他時刻 $time$ における $pos$ の取得や更新操作(平衡二分木への挿入) も $\O (\log n)$ 時間で処理することが可能.