Date
题目描述
Picks 认识 n 位女生,第 j 位女生的颜值为 aj。他计划进行 m 次约会。
第 i 次约会给定编号区间 [Li,Ri] 和颜值要求 Fi。他先从 1,2,…,Ri−Li+1 中等概率选一个整数 K,再从编号在 [Li,Ri] 内的女生中等概率选出 K 位(不重复)。
对每次约会,求选出的女生的颜值全都不低于 Fi 的概率,并将该概率乘以 105。
输入格式
第一行两个整数 n,m。第二行 n 个整数 a1,…,an。
接下来 m 行,第 i 行给出三个整数 Li,Ri,Fi,表示一次约会。
输出格式
输出 m 行。每行一个实数,为相应结果四舍五入保留三位小数后的值。
数据规模与约定
对于 30% 的数据,n≤100。
对于全部数据,1≤n,m≤105,1≤ai,Fi≤105,1≤Li≤Ri≤n。