#P9710. 获取名额

    ID: 6334 传统题 3000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-补事件计算对数化乘积为和级数截断近似一维前缀和ST 表阈值划分大小情况分治算法浮点补偿求和

获取名额

题目描述

共有 nn 场省选选拔,第 ii 场前 aia_i 名可获得资格。每次询问给出 l,r,xl,r,x,假定 Moorhsum 只参加第 ll 场到第 rr 场。各场名次相互独立,分别在整数 11 到 xx 中等概率取值。求他至少在一场获得资格的概率。

输入格式

第一行两个整数 n,qn,q,表示场数和询问次数。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 qq 行,每行三个整数 l,r,xl,r,x。

输出格式

每次询问输出一行概率,与标准答案的绝对误差不超过 10−610^{-6}。

样例

3 3
1 2 3
1 1 4
1 2 4
1 3 4
0.2500000000
0.6250000000
0.9062500000
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

样例 3 输入 · 样例 3 输出

数据范围

对于全部数据,1≤n,q≤6000001\le n,q\le 600000,1≤ai,x≤1091\le a_i,x\le10^9,1≤l≤r≤n1\le l\le r\le n,每次询问均满足 x>max⁡iaix>\max_i a_i。

  • 对于 20% 的数据,n,q≤500n,q\le500。
  • 对于 40% 的数据,n,q≤5000n,q\le5000。
  • 另有 30% 的数据,n,q≤100000n,q\le100000 且所有询问满足 l=1,r=nl=1,r=n。

原 PDF