问题陈述
给你一个长度-N 序列 A=(A _ 1,A _ 2,\ldots,A _ N) 非负整数和实数值 x 严格大于 0 且小于或等于 1.
对于整数对 (l,r)\ (1\leq l\leq r\leq N),我们定义 f(l,r) 如下:
答案 Q 查询。 在 i第一个查询 (1\leq i\leq Q),给定一个整数对 (l _ i,r _ i)\ (1\leq l _ i\leq r _ i\leq N),查找 f(l _ i,r _ i).
约束
- 1\leq N\leq2\times10 ^ 5
- 0\leq A _ i\leq10 ^ 9\ (1\leq i\leq N)
- 0\lt x\leq 1
- 1\leq Q\leq2\times10 ^ 5
- 1\leq l _ i\leq r _ i\leq N\ (1\leq i\leq Q)
- N,A _ i,Q,l _ i,和 r _ i 是整数。
- x 是一个实际值,最多 15 小数位。
输入
输入由标准输入按以下格式给出:
N A _ 1 A _ 2 \ldots A _ N x Q l _ 1 r _ 1 l _ 2 r _ 2 \vdots l _ Q r _ Q
输出
打印 Q 行。 的 i第行 (1\leq i\leq Q) 应包含该值 f(l _ i,r _ i) 为 i第一个查询 (l _ i,r _ i)。 如果与真实值的相对或绝对误差最多为,则您的答案被认为是正确的 10 ^ {-6}.
示例输入 1
7 3 1 4 1 5 9 2 0.25 4 1 3 3 6 1 7 2 2
示例输出 1
3.5 4.703125 3.54443359375 1
对于每个查询,答案如下。
- f(1,3)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2=3+0.25+0.25=3.5.
- f(3,6)=A _ 3\times0.25 ^ 0+A _ 4\times0.25 ^ 1+A _ 5\times0.25 ^ 2+A _ 6\times0.25 ^ 3=4+0.25+0.3125+0.140625=4.703125.
- f(1,7)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2+A _ 4\times0.25 ^ 3+A _ 5\times0.25 ^ 4+A _ 6\times0.25 ^ 5+A _ 7\times0.25 ^ 6=3+0.25+0.25+0.015625+0.01953125+0.0087890625+0.00048828125=3.54443359375.
- f(2,2)=A _ 2\times0.25 ^ 0=1.
因为如果相对或绝对误差最多为,则您的答案被认为是正确的 10 ^ {-6},输出如下
3.5 4.703125 3.54443359375 0.999999
和
3.4999965 4.703129703125 3.54443004931640625 1.000001
也被接受。
示例输入 2
15 6 45 81 83 28 40 31 30 51 31 59 50 94 36 0 0.998244353 20 1 2 1 5 1 10 2 5 2 10 3 3 3 8 3 12 4 4 4 14 5 5 5 11 5 13 5 14 6 7 7 7 8 10 10 13 10 14 12 14
示例输出 2
50.920995885 242.004326432639783195178618854259 422.764240065920208662445303267128 236.419395434977014285377699356 417.497217803865912440022892137641 81 292.066191815728552247199317241863 480.544234637661958884554506013369 83 528.144974561396676686531955107577 28 268.416129630805326045766513470066 410.492717775411750526215653552396 445.927866482402907904585917660160 70.945574943 31 111.801707440188046879 233.226782486727123857410847838 268.974634315843968519190799533618 179.708673560669989924