この問題を高速に解くために頻度列の考え方を利用します。
クエリ 1 の昇順ソートは、頻度を利用すると次のような操作に言い換えられます。

• \(A_L, \dots, A_R\) における \(x\) の登場回数を \(c_x\) とする。
• \(c_0, c_1, \dots, c_{10}\) を全て計算する。
• \(x=0, 1, \dots, 10\) の順に次の操作を行う。
  • \(A_L, \dots, A_{L + c_x - 1}\) を \(x\) に更新する。その後 \(L\) に \(c_x\) を足す。

クエリ \(2\), クエリ \(3\) についても \(c_0, c_1, \dots, c_{10}\) を利用した操作に言い換えられます。
よって、この問題は区間代入・区間和を高速に処理する問題に言い換えられます。この 2 種類のクエリは、遅延評価セグメント木などのデータ構造を利用すると、 \(A\) の要素の種類数を \(\sigma\) として前計算 \(\mathrm{O}(\sigma N)\) 、クエリあたり \(\mathrm{O}( \sigma \log N)\) で処理できます。 よってこの問題を計算量 \(\mathrm{O}(\sigma N + Q \sigma \log N)\) で解くことができて、十分高速です。
(より計算量の良い解法として平衡二分木の上に疎なセグメント木を載せた計算量 \(\mathrm{O}(N + Q (\log N + \log \sigma))\) の解法がありますが、この問題では要求していません。)