この問題は、Mo’s algorithm というテクニックを利用して解くことができます。

Mo’s algorithm

ある列に対し、「列の部分区間に対してなにかを求める」クエリがたくさん与えられる問題で、

• クエリがまとめて与えられる「オフライン」問題である
• 区間 \([L, R]\) に対する答えがわかっているとき、
  • 区間 \([L \pm 1, R]\) に対する答え
  • 区間 \([L, R \pm 1]\) に対する答え が高速に計算できる

とき、Mo’s algorithm によって、全てのクエリに対する答えを高速に求めることができます。

Mo’s algorithm とは以下のようなアルゴリズムです。

1. バケットの個数 \(B\) を \(\sqrt{Q}\) 個程度の値に定める。
2. 全てのクエリを、クエリの左端の値によって \(B\) 個のバケットに分割する。具体的には、クエリが \([l, r]\) の場合、これをバケット \(\left\lfloor\frac{(l - 1)B}{N}\right\rfloor\) に入れる。
3. 各バケットについて、以下を行う。
   1. バケット内のクエリを右端でソートし、\([l_1, r_1], …, [l_k, r_k]\) とする。(\(r_1 ≤ \dots ≤ r_k\))
   2. 空の区間から両端を伸び縮みさせることを繰り返し、区間 \([l_1, r_1]\) に対する答えを求める。
   3. そこから区間の両端を伸び縮みさせることを繰り返し、区間 \([l_2, r_2]\) に対する答えを求める。
   4. これを繰り返し、全ての区間に対する答えを求める。

• 右端の伸び縮みは、クエリが \(Q\) 個、クエリごとの移動幅が \(\frac NB\) 程度なので、合計で \(\frac{NQ}{B}\) 回程度
• 左端の伸び縮みは、バケットが \(B\) 個、バケットごとの移動幅が \(N\) 程度なので、合計で \(NB\) 回程度

したがって、\(B \in \Theta(\sqrt{Q})\) のとき、両端の伸び縮み \(O(N\sqrt{Q})\) 回で全てのクエリに対する答えを計算できます。

この問題の場合

この問題では、区間 \([L, R]\) に対し、\(f((A_L, \dots, A_R))\) の値を持ち、\((A_L, \dots, A_R)\) をソートした列を平衡二分探索木 (SortedSet) で管理すれば、両端の伸び縮みを \(O(\log N)\) で計算することができます。
これより、Mo’s algorithm を利用してこの問題を \(O(\sqrt{Q}\cdot N\log N)\) 時間で解くことができました。