A5947. 「2020-2021 集训队作业」Old Problem
编程题
NOI/NOI+/CTSC
知识点
题目描述
为参加省选，Moorhsum 必须通过省选选拔。
省选选拔共计 $n$ 场，第 $i$ 场的前 $a_i$ 名获得省选资格。
作为 Moorhsum 的好朋友，Goodeat 想算出如果 Moorhsum 只参加第 $l$ 场到第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机产生，那么他获得省选资格的概率。
但是 Goodeat 太莱了，于是他向你求助。你能帮帮他么？
省选选拔共计 $n$ 场，第 $i$ 场的前 $a_i$ 名获得省选资格。
作为 Moorhsum 的好朋友，Goodeat 想算出如果 Moorhsum 只参加第 $l$ 场到第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机产生，那么他获得省选资格的概率。
但是 Goodeat 太莱了，于是他向你求助。你能帮帮他么？
输入格式
第一行两个数 $n, q$ 代表选拔场数和询问次数
接下来 $n$ 个数 $a_1\sim a_n$ 每场的名额数
随后 $q$ 行，每行三个数 $l, r, x$
接下来 $n$ 个数 $a_1\sim a_n$ 每场的名额数
随后 $q$ 行，每行三个数 $l, r, x$
输出格式
对于每次询问，输出一个小数表示若 Moorhsum 只参加第 $l$ 场 $\sim$ 第 $r$ 场，且每一场的排名在 $[1,x]$ 中随机时获得名额的概率。
你的答案只要与标准答案差的绝对值在 $10^{-6}$ 以内即算正确。
你的答案只要与标准答案差的绝对值在 $10^{-6}$ 以内即算正确。
输入输出样例
输入 #1
3 3 1 2 3 1 1 4 1 2 4 1 3 4
输出 #1
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
输出 #2
0.9806625000 0.6646667215 0.6266061980 0.4417833108 0.0892857143 0.7695473251 0.0063826566
说明/提示
对于 $20\%$ 的数据 $n, q \leq 500$
对于 $40\%$ 的数据 $n, q \leq 5000$
另有 $30\%$ 的数据 $n, q \leq 100000$，$l = 1$，$r = n$
对于 $100\%$ 的数据 $1 \leq n, q \leq 600000$，$1 \leq x \leq 10^9$，$1 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$
由于 Moorhsum 显然不能稳进省选，数据保证对于**任意** $i$，$a_i < x$（即 $x > \max(a_1, a_2, ..., a_n)$）
对于 $40\%$ 的数据 $n, q \leq 5000$
另有 $30\%$ 的数据 $n, q \leq 100000$，$l = 1$，$r = n$
对于 $100\%$ 的数据 $1 \leq n, q \leq 600000$，$1 \leq x \leq 10^9$，$1 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$
由于 Moorhsum 显然不能稳进省选，数据保证对于**任意** $i$，$a_i < x$（即 $x > \max(a_1, a_2, ..., a_n)$）