総和の代わりに期待値を考えることにします。

\(E(t,i) := E[クエリをt個処理したあとのa_i]\) をまず考えることにします。また、

\(P(t,i,v) := P[(クエリをt個処理したあとのa_i) \geq v]\) とおき、対応する指示関数を\(X(t,i,v)\) とおきます。

\(a_i\) が \(0,\ldots,M-1\) の値しかとらないことから、 \(E(t,i) = \sum_{v=1}^{M-1} P(t,i,v)\) が成り立ちます。

\(t,i,v\) を固定して考えます。\(k\) 個目のクエリに対し、 意味がある というのを、 \(l_k \leq i \leq r_k\) かつ、 (maxクエリで \(v_k \geq v\) または minクエリで \(v_k < v\)) と定義します。

つまり、\(X(t,i,v)\) が変わりうるクエリということです。 意味のあるもののうち max クエリであれば必ず \(a_i \geq v\) に、 min クエリであれば必ず \(a_i < v\) になります。

意味があるクエリが一度も来なければ \(X(t,i,v) = 0\) であり、一度でも来る場合は、そのうち最後の一回がmaxクエリであることと \(X(t,i,v) = 1\) が同値なので、 確率 \((M-v)/M\) で \(X(t,i,v) = 1\), 確率\(v/M\) で \(X(t,i,v) = 0\) となります。 クエリに意味がある確率は \(v\) によらず \(p_i := \frac{i(N+1-i)}{\binom{N+1}{2}} \cdot \frac{M}{2M+1}\) なので、 \(P(t,i,v) = [1 - (1-p_i)^t] \cdot \frac{M-v}{M}\) と書け、さらに \(E(t,i) = [1 - (1-p_i)^t] \cdot \frac{M-1}{2}\) となります。

\(t+1\) 回目のクエリで \(E(t,i)\) が答えに寄与する条件は、sum クエリであって区間が \(i\) を含むことなので、確率は \(q_i := \frac{i(N+1-i)}{\binom{N+1}{2}} \cdot \frac{1}{2M+1}\) です。

結局 \(ans\) の期待値は \(\sum_{t=0}^{Q-1} \sum_{i=1}^{N} E(t,i) \cdot q_i\) で計算でき、これに計算した値たちを代入することで、\(NQ\) 項からなる式を得ます。 \(i\) を固定して \(t\) に関する和を取ると、等比数列の和のような形になっているのでこれはまとめて \(O(\log Q)\) で計算でき、全体で \(O(N \log Q)\) で答えが求まります。