UOJ Logo Zijian Online Judge

ZOJ

#34. 获取名额

统计

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

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

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

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

输入格式

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

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

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

输出格式

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

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

样例一

input

3 3 
1 2 3
1 1 4
1 2 4
1 3 4

output

0.2500000000
0.6250000000
0.9062500000

explanation

Moorhsum只参加第一场获得名额的概率为$1/4$

Moorhsum参加前两场获得名额的概率 = $第一场获得名额的概率$ + $第一场未获得名额第二场获得的概率$ = $1/4$ + $3/4 * 1/2$ = $5/8$

Moorhsum参加前三场获得名额的概率 = $前两场获得名额的概率$ + $前两场未获得名额第三场获得的概率$ = $5/8$ + $3/8 * 3/4$ = $29/32$

样例二

input

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

output

0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566

样例三

见样例数据下载

限制与约定

对于$20\texttt{%}$的数据 $n, q \leq 500$

对于$40\texttt{%}$的数据 $n, q \leq 5000$

另有$30\texttt{%}$的数据 $n, q \leq 100000$,$l = 1$,$r = n$

对于$100\texttt{%}$的数据 $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)$)

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载