まず、数列のとりうる値が大きいので、座標圧縮をしておく。そして、次のような配列をもっておく。
また、区間 $ \lbrack l, r) $ に対する $ cnt_{i}$ の値を $ cnt_{i} (l, r) $ とすると、クエリ $ \lbrack l, r)$ に対する答え $ f (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)を持っておき、クエリごとに次の順で操作を行う。
計算量を解析してみる。
よって、この操作の計算量は$O((N+Q) \sqrt{N})$になり、余裕を持って通すことが出来る。
ACコード
このアルゴリズムは Rollback平方分割 と名がつけられているらしいです。
追加が軽くて、削除が重いときはこれを使うとよさそう