RollbackMo
クラス · Mo’s algorithm (rollback)
struct RollbackMo;
概要
Mo’s algorithm (rollback)
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
長さnの列に対するrollback Moを構築する | $O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
input |
標準入力からq個の区間を追加する | $O(q)$ |
add |
半開区間を追加する | 償却 $O(1)$ |
solve |
(1) 左右共通の追加処理とロールバックで全クエリを実行する (2) 左右別の追加処理とロールバックで全クエリを実行する |
クエリ数を $q$ として、整列は $O(q\log q)$、 コールバック呼び出しは $O((n+q)\sqrt q)$ 回 |
メンバの詳細
input
void input(int q, int origin = 1, bool closed = false);
標準入力からq個の区間を追加する
- パラメータ
q: 読み込む区間の個数 - パラメータ
origin: 入力の添字の起点（1-indexedなら1、0-indexedなら0） - パラメータ
closed: 入力が閉区間 $[l, r]$ ならtrue、半開区間 $[l, r)$ ならfalse - 計算量: $O(q)$
solve
// (1)
template <class F, class G, class H, class I>
void solve(F add, G save, H load, I answer);
// (2)
template <class F, class G, class H, class I, class J>
void solve(F add_left, G add_right, H save, I load, J answer);
(1) 左右共通の追加処理とロールバックで全クエリを実行する
- 計算量: クエリ数を $q$ として、整列は $O(q\log q)$、 コールバック呼び出しは $O((n+q)\sqrt q)$ 回
(2) 左右別の追加処理とロールバックで全クエリを実行する
- 計算量: クエリ数を $q$ として、整列は $O(q\log q)$、 コールバック呼び出しは $O((n+q)\sqrt q)$ 回