A85972.「2020-2021 集训队作业」Old Problem

NOI/NOI+/CTSC

通过率：0%

时间限制：3.00s

内存限制：512MB

为参加省选，Moorhsum 必须通过省选选拔。

省选选拔共计 $n$ 场，第 $i$ 场的前 $a_i$ 名获得省选资格。

作为 Moorhsum 的好朋友，Goodeat 想算出如果 Moorhsum 只参加第 $l$ 场到第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机产生，那么他获得省选资格的概率。

但是 Goodeat 太莱了，于是他向你求助。你能帮帮他么？

第一行两个数 $n, q$ 代表选拔场数和询问次数

接下来 $n$ 个数 $a_1\sim a_n$ 每场的名额数

随后 $q$ 行，每行三个数 $l, r, x$

对于每次询问，输出一个小数表示若 Moorhsum 只参加第 $l$ 场 $\sim$ 第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机时获得名额的概率。

你的答案只要与标准答案差的绝对值在 $10^{-6}$ 以内即算正确。

输入#1

输出#1

0.2500000000
0.6250000000
0.9062500000

输入#2

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

输出#2

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, ..., a_n)$ ）