以下では、クエリの添字を 0-indexed とします。 すなわち、クエリを \(\langle x_0, x_1, \dots, x_{Q-1}\rangle\) とします。

クエリを \(b\) 個ごとに分割することを考えます。 分割の \(i\) ブロック目は \(\langle x_{bi}, x_{bi+1}, \dots, x_{bi+(b-1)}\rangle\) です。 \(i\) ブロック目に含まれる整数の集合を \(S_i = \{x_{bi}, x_{bi+1}, \dots, x_{bi+(b-1)}\}\) とすると、\(|S_i| \le b\) です。

\(i\) ブロック目に含まれない値 \(j\notin S_i\) に関しては、\(i\) ブロック目のクエリの処理前後の \(A_j\) の差が共通なので、それを \(d_i\) とおきます。

\(i\) ブロック目の各クエリに対して、下記を行います。

• \(d_i\) にその時点での \(|S|\) を加算する。
• 各 \(j\in S\wedge S_i\) に対して、\(A_j\) に \(|S|\) を加算する。

\(i\) ブロック目の各クエリを処理し終えたら、各 \(j\in \{1, 2, \dots, N\}\smallsetminus S_i\) に対して \(A_j\) に \(d_i\) を加算します。

各ブロックに対して \(O((b^2+N)\cdot \frac Qb) = O(Q(b+N/b))\) 時間で処理できるため、\(b = \Theta(\sqrt N)\) とすると、全体で \(O(Q\sqrt N)\) 時間となります。