JOI 2013/2014 春合宿 day1-3 歴史の研究
問題
TLE解法
まず、数列のとりうる値が大きいので、座標圧縮をしておく。そして、次のような配列をもっておく。
- $ cnt_{i}$ : 今見ている区間に対する、座標圧縮後の値$ i$の出現回数
- $ z_{i}$ : $ i$の圧縮前の値
また、区間 $ \lbrack l, r) $ に対する $ cnt_{i}$ の値を $ cnt_{i} (l, r) $ とすると、クエリ $ \lbrack l, r)$ に対する答え $ f (l, r) $ は、
- $ f(l, r) = \max ( z_{i} \cdot cnt_{i} ( l, r) ) $
になる。
$ z_{i} \cdot cnt\_{i} ( l, r) $ の値をmultisetで管理すると、最大値の取得、区間の伸縮が $ O(\log N)$ で行えるので、Mo's algorithmを使うことによって、全体で $ O( ( N + Q) \sqrt{N} \log N)$ で問題を解くことができる。
この解法を実装するとTLEしてしまった(定数倍が小さければ通るかもしれない)。
計算量改善
上の解法のネックは、区間を縮める操作に対応するためにすべての値をmultisetで持っておく必要があるところ。区間を広げる操作のみを行えば、解は単調に増加するので最大値以外を持っておく必要がない。
そこで、Moを少し改変してみることにする。左端を $ \sqrt{N}$ ずつのブロックに分け、ブロックが同じところでは右端でソートするというところまでは同じ。
ただし、クエリの処理はブロックごとに独立に行う(リセットする)ことにする。こうすると、$r$ は単調増加になるので、右端は考慮しなくてよい。
左端はどうするかというと、初期位置を次のブロックとの境界にしておく。区間の答え $ x$ (初期値0)を持っておき、クエリごとに次の順で操作を行う。
- 右端を右に動かしながら $ cnt, x$ を更新する(このときの $ x$ を保存しておく)
- 左端を左に動かしながら $ cnt, x$ を更新する(このときの $ x$ がクエリの答え)
- 左端を右に動かし初期位置に戻す( $ x$ を1.の時点のものに戻す)
計算量を解析してみる。
- 初期位置の操作 : $ \sqrt{N}$個のブロックごとに最大N回操作するので$ O(N \sqrt{N})$
- 1.の操作 : $ \sqrt{N}$個のブロックごとに最大N回操作するので$ O(N \sqrt{N})$
- 2.の操作 : クエリごとに最大$ \sqrt{N}$ 回操作するので$ O(Q \sqrt{N})$
- 3.の操作 : クエリごとに最大$ \sqrt{N}$ 回操作するので$ O(Q \sqrt{N})$
よって、この操作の計算量は$O((N+Q) \sqrt{N})$になり、余裕を持って通すことが出来る。
ACコード
最後に
このアルゴリズムは Rollback平方分割 と名がつけられているらしいです。
追加が軽くて、削除が重いときはこれを使うとよさそう