AT_past19_n.有限べき級数

给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$，以及一个实数 $x$，满足 $0 < x \leq 1$。

对于任意整数对 $(l, r)\ (1 \leq l \leq r \leq N)$，定义 $f(l, r)$ 如下：

[
\begin{aligned}
f(l, r) &= A_l + A_{l+1}x + A_{l+2}x^2 + \cdots + A_r x^{r-l} \
&= \sum_{i=0}^{r-l} A_{i+l} x^i
\end{aligned}
]

现在有 $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)$。

输入按如下格式从标准输入读入：

$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)$ 输出对第 $i$ 次询问 $(l_i, r_i)$ 计算得到的 $f(l_i, r_i)$。

只要你的输出的相对或绝对误差不超过 $10^{-6}$，就会被认为是正确答案。

样例解释 1

对于每个询问，答案如下。

• $f(1,3) = A_1 \times 0.25^0 + A_2 \times 0.25^1 + A_3 \times 0.25^2 = 3 + 0.25 + 0.25 = 3.5$。
• $f(3,6) = A_3 \times 0.25^0 + A_4 \times 0.25^1 + A_5 \times 0.25^2 + A_6 \times 0.25^3 = 4 + 0.25 + 0.3125 + 0.140625 = 4.703125$。
• $f(1,7) = A_1 \times 0.25^0 + A_2 \times 0.25^1 + A_3 \times 0.25^2 + A_4 \times 0.25^3 + A_5 \times 0.25^4 + A_6 \times 0.25^5 + A_7 \times 0.25^6 = 3 + 0.25 + 0.25 + 0.015625 + 0.01953125 + 0.0087890625 + 0.00048828125 = 3.54443359375$。
• $f(2,2) = A_2 \times 0.25^0 = 1$。

由于只要相对或绝对误差不超过 $10^{-6}$ 也是正确答案，所以如

3.5
4.703125
3.54443359375
0.999999

以及

3.4999965
4.703129703125
3.54443004931640625
1.000001

等均会被认为是正确答案。

数据范围

• $1\leq N\leq 2\times 10^5$
• $0\leq A_i\leq 10^9\ (1\leq i\leq N)$
• $0 < x \leq 1$
• $1\leq Q\leq 2\times 10^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$ 位小数

由 ChatGPT 5 翻译