概要
解法
Mo のアルゴリズムを使います。
区間に対して、
- 各値がいくつ含まれているか
- その区間に対する hash 値
を管理します。区間の長さがひとつ伸びたり縮めたりしたときの更新は、$O(1)$ 時間で行えます。よって、Mo’s algorithm により本問題は $O((N+Q)\sqrt{N})$ 時間で解くことができます。
スコアの計算では、$x^n \pmod{10^9+7}$ という種類の値が必要になりますが、必要になる $x^n$ は $O(N)$ 種類しかなくて、同じ $x$ に対して $n$ 昇順で計算すればひとつあたり $O(1)$ 時間です。毎回二分累乗法をやると、余分に $\log \text{mod}$ 倍がつきます。
参考文献
Mo’s algorithm について説明されているものをいくつか挙げておきます。
