题解

思路

查询同时带有等差下标和线性权值。小 $k$ 可以直接枚举；对一般数据按步长大小分治：大步长对应很短的序列，小步长则复用同一步长的后缀动态规划。

做法

子任务 1：连续段的两个前缀和

当所有查询的 $d=1$ 时，令

$$P_i=\sum_{j=1}^{i}a_j,\qquad Q_i=\sum_{j=1}^{i}j a_j.$$

对于右端点 $r=s+k-1$，查询答案为

$$(Q_r-Q_{s-1})-(s-1)(P_r-P_{s-1}).$$

预处理和每次查询分别为 $O(n)$、$O(1)$，总复杂度为 $O(n+q)$。

子任务 2：直接枚举取出的元素

按定义枚举 $j=0,1,\ldots,k-1$，累加 $(j+1)a_{s+jd}$。由于 $k\le300$，总复杂度为 $O(\sum k)$，至多约为 $O(300q)$。

子任务 3：按步长分组的根号动态规划

取阈值 $B=\lfloor\sqrt n\rfloor+1$。

• 若 $d>B$，合法性保证 $k\le n/d<B+1$，直接枚举一次查询只需 $O(B)$。
• 若 $d\le B$，把相同步长的查询放在一起，并为这个 $d$ 从右向左计算：

$$S_i=a_i+S_{i+d},\qquad W_i=S_i+W_{i+d}.$$

于是 $S_i$ 是从 $i$ 开始、步长为 $d$ 的后缀元素和，$W_i$ 是同一后缀按 $1,2,3,\ldots$ 加权后的和。一次长度为 $k$ 的查询需要删去从 $i+kd$ 开始的后缀。该后缀在 $W_i$ 中的权值整体多了 $k$，所以

$$\operatorname{ans}=W_s-W_{s+kd}-kS_{s+kd}.$$

每个出现过的小步长只做一次 $O(n)$ 动态规划。总时间复杂度为 $O(nB+qB)$，额外空间复杂度为 $O(n+q)$。

所有乘法和答案都必须使用 64 位有符号整数；答案绝对值可达到约 $5\times10^{17}$。

复杂度

• 子任务 1：时间 $O(n+q)$，空间 $O(n)$。
• 子任务 2：时间 $O(\sum k)$，空间 $O(n)$。
• 满分做法：时间 $O((n+q)\sqrt n)$，空间 $O(n+q)$。