CF523B Mean Requests

本题源于 VK 社交网络使用的实际算法问题。 与其他高负载网站一样，VK 的开发人员定期处理请求统计。一个重要的负载指标是某个时间段内（例如 $T=60$ 秒即 1 分钟，或 $T=86400$ 秒即 1 天）的平均请求数。当这个值严重下降时，可能表示网站访问存在问题；而当这个值上升时，可能需要分析增长原因，并在必要时增加服务器。 但是，在处理大型社交网络的海量数据时，计算一个时间段内的平均请求数也面临挑战。因此，开发人员采用了一些创新技术，既能接近真实值，又能提升效率。 我们考虑以下模型。假设服务运行了 $n$ 秒。我们已知在每个时间点 $t$（$1 \le t \le n$）对该资源的请求数 $a_t$。定义一个利用指数衰减的平均数计算算法，设 $c$ 为大于 1 的实数。 ```cpp // 正确设置常数 c 可以调整所统计的时间范围 double c = ; // 该变量将保存当前时刻前 T 秒内的平均请求数 double mean = 0.0; for t = 1..n: // 每秒进行如下操作： // $a_t$ 是这一秒的请求数 mean = (mean + $a_t$ / T) / c; ``` 如此，每秒都会根据当前秒的请求数更新 `mean` 变量。通过适当选择常数 $c$，可使 `mean` 的值接近于 $t-T+1 \le x \le t$ 之间的真实平均值 $a_x$。 这种方法的优点在于只需当前时刻的请求数，无需保存长时间的历史请求。同时，它给较新的数据更高权重，有助于快速应对数据剧变。 在工业编程中采用新理论方法前，必须在给定测试集上验证其实际可信度。你的任务是将近似算法结果与真实数据进行比较。 你会收到 $n$ 个值 $a_t$，整数 $T$ 和实数 $c$。此外，还给定 $m$ 个时刻 $p_j$（$1 \le j \le m$），我们关注的是过去 $T$ 秒的平均请求数。实现两个算法：一个按定义计算所需值，即通过公式 $$ \text{real} = \frac{1}{T} \sum_{x=t-T+1}^{t} a_x $$ 另一个按上述方法计算均值。输出这两个值，并通过公式 $$ \text{error} = \left| \frac{\text{approx} - \text{real}}{\text{real}} \right| $$ 计算第二个算法的相对误差，其中 $\text{approx}$ 是第二个算法的近似值，$\text{real}$ 是第一个算法的真实值。

输入包括： 第一行，三个数：整数 $n$（$1 \le n \le 2 \times 10^5$）、$T$（$1 \le T \le n$）及实数 $c$（$1 < c \le 100$），其代表需要工作的时间范围、统计请求的时间段长度，以及近似算法的系数 $c$。$c$ 精确到小数点后六位。 第二行，有 $n$ 个整数 $a_t$（$1 \le a_t \le 10^6$），表示每个时间点的请求数。 第三行，整数 $m$（$1 \le m \le n$），表示我们关注的时刻个数。 第四行，有 $m$ 个整数 $p_j$（$T \le p_j \le n$），它们表示需要统计的时刻，且按递增顺序排列。

输出 $m$ 行。第 $j$ 行包含三个数：$\text{real}$、$\text{approx}$ 和 $\text{error}$，具体为： - $\text{real}$ 是过去 $T$ 秒的真实平均请求数； - $\text{approx}$ 为给定算法计算的近似均值，对应时刻 $t=p_j$ 时的 $\text{mean}$ 值； - $\text{error}$ 是近似算法的相对误差。 输出数字和正确答案相比，允许的相对或绝对误差为 $10^{-4}$。建议输出时保留至少五位小数。 **本翻译由 AI 自动生成**