古い問題 - المسألة

省選に参加するため、Moorhsum は省選選抜を通過しなければなりません。

省選選抜は合計 $n$ 回行われ、第 $i$ 回の選抜では上位 $a_i$ 名が省選の資格を得ます。

Moorhsum の友人である Goodeat は、もし Moorhsum が第 $l$ 回から第 $r$ 回までの選抜のみに参加し、各回の順位が $[1, x]$ の範囲でランダムに決まると仮定した場合、彼が省選の資格を得る確率を計算したいと考えています。

しかし、Goodeat にはそれが難しいため、あなたに助けを求めています。彼を助けてあげてください。

1 行目に選抜回数 $n$ とクエリ数 $q$ が与えられます。

続く $n$ 個の数値 $a_1 \sim a_n$ は、各回の選抜枠数です。

その後の $q$ 行には、各クエリとして $l, r, x$ が与えられます。

各クエリに対し、Moorhsum が第 $l$ 回から第 $r$ 回までの選抜のみに参加し、各回の順位が $[1, x]$ の範囲でランダムに決まると仮定したときに、省選の資格を得る確率を小数で出力してください。

答えは標準解答との絶対誤差が $10^{-6}$ 以内であれば正解とみなされます。

0.2500000000
0.6250000000
0.9062500000

Moorhsum が第 1 回のみ参加して資格を得る確率は $1/4$ です。

Moorhsum が第 1 回と第 2 回に参加して資格を得る確率は、第 1 回で資格を得る確率 $+$ 第 1 回で資格を得られず第 2 回で資格を得る確率 $= 1/4 + 3/4 \times 1/2 = 5/8$ です。

Moorhsum が第 1 回から第 3 回まで参加して資格を得る確率は、第 1 回・第 2 回で資格を得る確率 $+$ 第 1 回・第 2 回で資格を得られず第 3 回で資格を得る確率 $= 5/8 + 3/8 \times 3/4 = 29/32$ です。

10 7
3 7 19 6 8 7 2 3 5 4
1 4 20
4 6 23
5 7 21
4 10 63
9 9 56
3 4 27
1 10 10000

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

配布ファイルを参照してください。

データセットの $20\%$ について、$n, q \leq 500$ です。

データセットの $40\%$ について、$n, q \leq 5000$ です。

また、データセットの $30\%$ について、$n, q \leq 100000$ かつ $l = 1, r = n$ です。

データセットの $100\%$ について、$1 \leq n, q \leq 600000$、$1 \leq x \leq 10^9$、$1 \leq a_i \leq 10^9$、$1 \leq l \leq r \leq n$ です。

Moorhsum が確実に省選へ進めるわけではないため、すべての $i$ に対して $a_i < x$（すなわち $x > \max(a_1, a_2, \dots, a_n)$）であることが保証されています。

QOJ.ac