この問題は (列の)平方分割 と呼ばれるテーマを扱った問題です。

平方分割とは？

(列の)平方分割とは、長さ \(N\) の列を \(\mathrm{O}(\sqrt{N})\) 個の バケット に分割して管理することで列上のクエリを処理するデータ構造のことをいいます。

簡単な例を挙げて説明しましょう。
数列 \((A_1, A_2, \dots, A_{100})\) があって、次の 2 種類のクエリを処理したいとします。

• \(i, x\) が与えられるので \(A_i\) を \(x\) に更新
• \(L, R\) が与えられるので \(\sum_{i=L}^R A_i\) を計算

この時、要素を \(10\) 個ずつのバケットに分けて、各バケット内の要素の和を別途管理するのが平方分割です。すなわち、

• \(B_1 = A_1 + A_2 + \dots + A_{10}\)
• \(B_2 = A_{11} + A_{12} + \dots + A_{20}\)
• \(\vdots\)
• \(B_{10} = A_{91} + A_{92} + \dots + A_{100}\)

として \(B_1, B_{2}, \dots, B_{10}\) を適切に管理すると、例えば \((L, R) = (39, 61)\) の時は

\[\sum_{i=39}^{61} A_i = A_{39} + A_{40} + B_5 + B_6 + A_{61}\]

となるので \(A, B\) を合わせて使えば高速に和を計算できる、という要領です。
計算量は今回の場合は次のようになります。

• 要素の更新は \(A, B\) を適切に差分更新すれば \(\mathrm{O}(1)\)
• 区間和の取得は最大で \(\mathrm{O}(\sqrt{N})\) 個の要素を足すことになるので \(\mathrm{O}(\sqrt{N})\)

ここで、読者の方は「Segment tree や Fenwick tree でいいのでは？」と思うかもしれません。実際これはその通りで、今回の例も含めてたいていの区間クエリは平方分割を使用せずとも Segment tree や Fenwick tree で事足ります。そして、クエリあたり最悪 \(\mathrm{O}(\sqrt{N})\) かかる平方分割に比べて、対数時間で済む Segment tree や Fenwick tree の方が優秀な場面が多いです。
しかし、クエリの種類によっては Segment tree に乗るようなモノイドを設計することが不可能な場合があり、その場合に平方分割が有力な選択肢の 1 つとなります。

今回の問題は、そうした例ともまた異なる、少しひねった平方分割のユースケースを紹介する問題です。(ここで「ひねった」と書きましたが、データ構造の計算量改善においては典型的な方法でもあります。) どのように平方分割を使用するか説明していきましょう。

解法

さて、今回の問題の解法に移りましょう。

まず、今回の問題は Mo’s algorithm および Segment Tree を使用すれば \(\mathrm{O}((N \sqrt{Q} + Q) \log N)\) で解くことができます。

• Mo’s algorithm を知らない方は以下の問題の解説などを参照してください。例題 1, 例題 2, 例題 3

解法を簡潔に説明すると、区間内に登場する \(x\) の個数を \(f_x\) \((1 \leq x \leq N)\) としたときに \(f_x\) の総和および \(\frac{1}{f_x !}\) の総積を Segment tree で管理すればよいです。計算量は次の通りです。

• \(N \sqrt{Q}\) 回の区間の伸縮のたびに \(\mathrm{O}(\log N)\) かけて Segment tree を更新するので \(\mathrm{O}(N \sqrt{Q} \log N)\)
• \(Q\) 回の答えの計算のたびに \(\mathrm{O}(\log N)\) かけて Segment tree の区間積を取得するので \(\mathrm{O}(Q \log N)\)
• よって全体で \(\mathrm{O}((N \sqrt{Q} + Q) \log N)\)

しかしこの方針ではおそらく実行時間制限に間に合わないでしょう。

そこで、Segment Tree を使用していた部分を平方分割に差し替えます。一見するとこれは損なようですが、計算量評価をしてみると次のようになります。

• \(N \sqrt{Q}\) 回の区間の伸縮のたびに \(\mathrm{O}(1)\) かけてバケットを更新するので \(\mathrm{O}(N \sqrt{Q})\)
• \(Q\) 回の答えの計算のたびに \(\mathrm{O}(\sqrt{N})\) かけて区間積を取得するので \(\mathrm{O}(Q \sqrt{N})\)
• よって全体で \(\mathrm{O}(N \sqrt{Q} + Q \sqrt{N})\)

よって \(N=Q\) とすると計算量が \(\mathrm{O}(N^{1.5} \log N)\) から \(\mathrm{O}(N^{1.5})\) に落ちているのです！
以上の内容を適切に実装することでこの問題を解くことができます。\(\mathrm{O}(\log N)\) 倍の高速化を要求する関係上、実行時間制限は通常の問題より厳しいですが、Mo’s algorithm の探索順で定数倍を悪くしなければ十分余裕を持って AC できると思います。