UndoSlopeTrick
クラス · Undo 可能 slope trick
template <class T>
struct UndoSlopeTrick;
概要
Undo 可能 slope trick
以下では $N$ を、これまでに行った add_x_minus_a / add_a_minus_x （add_abs は内部で両方呼ぶため 2 回分）の呼び出し回数とする
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
$f(x)=0$ の状態を構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
min_x |
最小値を取る $x$ の 1 つを返す | $O(1)$ |
min_value |
関数の最小値を返す | $O(1)$ |
add_const |
$f(x) \gets f(x) + a$ | $O(1)$ |
add_x_minus_a |
$f(x) \gets f(x) + \max(0, x - a)$ | $O(\log N)$ |
add_a_minus_x |
$f(x) \gets f(x) + \max(0, a - x)$ | $O(\log N)$ |
add_abs |
$f(x) \gets f(x) + |x - a| = f(x) + \max(0, x - a) + \max(0, a - x)$ | $O(\log N)$ |
undo |
直前の add_* 操作の内部履歴を 1 件取り消す |
$O(\log N)$ |
snapshot |
現在の状態を表す履歴位置を返す | $O(1)$ |
rollback |
snapshot() で取得した時点まで巻き戻す |
現在の履歴サイズを $h$ として $O((h - t) \log N)$ |