数列 \(A\) のある区間 \([l, r]\) における、

• 各整数の出現回数と、
• 問題文中の条件を満たす \(3\) つ組 \((i, j, k)\) の個数

がわかっているとき、区間の左端 \(l\) または右端 \(r\) を \(1\) だけ増減させた区間における上記の \(2\) つの情報も、差分更新によって \(O(1)\) 時間で得られます。 よって、Mo のアルゴリズムによって本問題を解くことができます。

・Moのアルゴリズムについて

Mo のアルゴリズムについて簡単に説明します。 対象の数列 \(A\) の長さを \(N\) とし、\((A_0, A_1, \ldots, A_{N-1})\) のように \(0\)-indexed とします。 また、下記の性質を仮定します。

区間 \([l, r]\) におけるクエリ（単にクエリ \([l, r]\) と呼ぶ）の答えが既知のとき、\(l\) または \(r\) を \(1\) だけ増減させた区間におけるクエリの答えが高速に（ここでは簡単のため \(O(1)\) 時間とする）求められる。

このとき、直前のクエリ \([l, r]\) に答えた後、そこから \(l\) または \(r\) を \(1\) 増減させることを繰り返して、左端を \(l \rightarrow l'\) 、右端を \(r \rightarrow r'\) と変化させることで、次のクエリ \([l', r']\) の答えを合計 \(O(|l'-l| + |r'-r|)\) 時間で得られます。

この方法で、クエリを与えられた順 \([l_1, r_1], [l_2, r_2], \ldots, [l_Q, r_Q]\) に答えると、各 \([l_i, r_i] \rightarrow [l_{i+1}, r_{i+1}]\) の変形は最悪 \(\Theta(N)\) 時間かかり、アルゴリズム全体で最悪 \(\Theta(QN)\) 時間かかりますが、Mo のアルゴリズムではクエリを並べ替えて答える順番を工夫することでこれを高速化します。（したがって、すべてのクエリが事前に与えられている必要があります。）

具体的には、\(Q\) 個のクエリ \([l, r]\) に答える順番を下記の通りに定めます。

正の整数 \(B\) を固定し、各クエリを \(\lfloor l / B \rfloor\) の小さいものほど先に、 さらに \(\lfloor l/ B\rfloor\) が等しいもの同士では \(r\) が小さいものほど先に、クエリに答える。

このときの時間計算量を以下で評価します。

まず、左端 \(l\) の移動回数を数えます。 変形 \([l_i, r_i] \rightarrow [l_{i+1}, r_{i+1}]\) のうち、

• \(\lfloor l_i/ B\rfloor = \lfloor l_{i+1}/ B\rfloor\) である変形はアルゴリズム全体で \(O(Q)\) 回あり、\(1\) 回あたりの左端の移動回数は \(O(B)\) です。

• \(\lfloor l_i/ B\rfloor \lt \lfloor l_{i+1}/ B\rfloor\) である変形はアルゴリズム全体で \(O(N/B)\) 回あり、\(1\) 回あたりの左端の移動回数は \(O(N)\) です。

次に、右端 \(r\) の移動回数を数えます。 変形 \([l_i, r_i] \rightarrow [l_{i+1}, r_{i+1}]\) のうち、

• まず、\(\lfloor l_i/ B\rfloor = \lfloor l_{i+1}/ B\rfloor\) である変形について考えます。 \(\lfloor l/ B\rfloor\) が等しいもの同士では \(r\) が小さい順にクエリに答える、つまり、\(\lfloor l/ B\rfloor\) が等しいクエリのまとまりを処理する間は \(r\) は単調に増加することから、\(\lfloor l/ B\rfloor\) が等しいクエリのまとまり \(1\) つことに右端の移動回数は \(O(N)\) 回です。 \(\lfloor l/ B\rfloor\) の値は \(O(N/B)\) 種類ある、つまり、まとまりの総数は \(O(N/B)\) なので、すべてのまとまりを合わせた右端の移動回数は \(O(N^2/B)\) 回です。

• \(\lfloor l_i/ B\rfloor \lt \lfloor l_{i+1}/ B\rfloor\) である変形はアルゴリズム全体で \(O(N/B)\) 回あり、\(1\) 回あたりの右端の移動回数は \(O(N)\) です。

以上より、アルゴリズム全体の計算時間は \(O(QB + N^2/B)\) 時間です。 よって、\(B\) を \(N/\sqrt{Q}\) 程度にとることで、\(O(N\sqrt{Q})\) 時間ですべてのクエリに答えることができます。