平方分割で解けます。

\(A\) を \(B\) 個の区間に分けます。それぞれの区間に対して以下の情報を持ちます。

• 数の和
• \(0\)〜\(10\) がそれぞれ何個あるか
• その区間が昇順ソートされているか、降順ソートされているか、どちらでもないか(どちらでもないときは、順番を全部記録しておく)

クエリ \(1,2\) は以下のように処理します。

\(i=1,2,...,B\) に対して、

まず、 \([L,R]\) に含まれている \(i\) の数を \(c_{i}\) として、それらをまず求める。

\(i=1,2,...,B\) に対して、

• 区間が \([L,R]\) と共通部分を持たないときはスルーする。
• 区間の全てが \([L,R]\) に含まれているなら区間内にある \(i\) の数をそれぞれ \(c_{i}\) に足す。
• それ以外なら区間内の順番を復元して、 \([L,R]\) 内に含まれている \(i\) の数を数える。

最後の操作は \(1\) クエリに対して \(2\) 回しかおこなられないため、 \(O(\sigma B+\frac{N}{B})\) で処理できます。

\(c_{i}\) がもとまったらそれをもとに \([L,R]\) の区間に対応させます。

この処理は \(O(\sigma + B + \frac{N}{B})\) で処理できます。

クエリ \(3\) は以下のように処理します。

\(i=1,2,...,B\) に対して、

• 区間が \([L,R]\) と共通部分を持たないときはスルーする。
• 区間の全てが \([L,R]\) に含まれているなら数の和を答えに足す。
• それ以外なら区間内の順番を復元して、 \([L,R]\) 内に含まれている部分を愚直に足す。

最後の操作は \(1\) クエリに対して \(2\) 回しかおこなられないため、 \(O(B+\frac{N}{B})\) で処理できます。

以上より空間計算量 \(O(\sigma B+N)\) 時間計算量 \(O(Q(\sigma B +\frac{N}{B}))\)

で処理できます。

\(B=\sqrt{\frac{N}{\sigma}}\) とすると、時間計算量は \(O(Q\sqrt{N\sigma})\) となります。

実装例 c++