#1938. Old Problem
Old Problem
Old Problem
题目描述
标题: Old Problem - Problem - QOJ.ac
#13462. Old Problem
The problem was used in the following contests:
为参加省选,Moorhsum 必须通过省选选拔。
省选选拔共计 n 场,第 i 场的前 ai 名获得省选资格。
作为 Moorhsum 的好朋友,Goodeat 想算出如果 Moorhsum 只参加第 l 场到第 r 场,且每一场的排名在 [1,x] 中随机产生,那么他获得省选资格的概率。
但是 Goodeat 太莱了,于是他向你求助。你能帮帮他么?
输入格式
第一行两个数 n,q 代表选拔场数和询问次数
接下来 n 个数 a1∼an 每场的名额数
随后 q 行,每行三个数 l,r,x
输出格式
对于每次询问,输出一个小数表示若 Moorhsum 只参加第 l 场 ∼ 第 r 场,且每一场的排名在 [1,x] 中随机时获得名额的概率。
你的答案只要与标准答案差的绝对值在 10−6 以内即算正确。
样例数据
样例 1 输入
3 3
1 2 3
1 1 4
1 2 4
1 3 4
样例 1 输出
0.2500000000
0.6250000000
0.9062500000
样例 1 解释
Moorhsum 只参加第一场获得名额的概率为 1/4
Moorhsum 参加前两场获得名额的概率 = 第一场获得名额的概率 + 第一场未获得名额第二场获得的概率 =1/4+3/4×1/2=5/8
Moorhsum 参加前三场获得名额的概率 = 前两场获得名额的概率 + 前两场未获得名额第三场获得的概率 =5/8+3/8×3/4=29/32
样例 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
样例 3
见下发文件。
子任务
对于 20% 的数据 n,q≤500
对于 40% 的数据 n,q≤5000
另有 30% 的数据 n,q≤100000,l=1,r=n
对于 100% 的数据 1≤n,q≤600000,1≤x≤109,1≤ai≤109,1≤l≤r≤n
由于 Moorhsum 显然不能稳进省选,数据保证对于任意 i,ai<x(即 x>max(a1,a2,...,an))
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 3
1 2 3
1 1 4
1 2 4
1 3 4
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
0.9806625000
0.6646667215
0.6266061980
0.4417833108
0.0892857143
0.7695473251
0.0063826566