#1938. Old Problem

    ID: 1938 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2294来源:qoj.ac数据:公开样例动态规划前缀和

Old Problem

Old Problem

题目描述

标题: Old Problem - Problem - QOJ.ac

#13462. Old Problem

Statistics

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