#P4191. Date

    ID: 3406 传统题 1000ms 256MiB 尝试: 24 已通过: 14 难度: 6 上传者: 标签>难度分类提高概率与期望全概率公式组合数学Pascal 递推数据结构可持久化线段树路径复制前缀版本作差CF2100

Date

Date

题目描述

Picks 认识 nn 位女生,第 jj 位女生的颜值为 aja_j。他计划进行 mm 次约会。

第 ii 次约会给定编号区间 [Li,Ri][L_i,R_i] 和颜值要求 FiF_i。他先从 1,2,…,Ri−Li+11,2,\ldots,R_i-L_i+1 中等概率选一个整数 KK,再从编号在 [Li,Ri][L_i,R_i] 内的女生中等概率选出 KK 位(不重复)。

对每次约会,求选出的女生的颜值全都不低于 FiF_i 的概率,并将该概率乘以 10510^5。

输入格式

第一行两个整数 n,mn,m。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 mm 行,第 ii 行给出三个整数 Li,Ri,FiL_i,R_i,F_i,表示一次约会。

输出格式

输出 mm 行。每行一个实数,为相应结果四舍五入保留三位小数后的值。

数据规模与约定

对于 30%30\% 的数据,n≤100n\le100。

对于全部数据,1≤n,m≤1051\le n,m\le10^5,1≤ai,Fi≤1051\le a_i,F_i\le10^5,1≤Li≤Ri≤n1\le L_i\le R_i\le n。