# 世纪轰炸机：题解

## 解法比较

分块、卷积和直接累计适用于不同的参数范围，作为并列方案。标程采用直接累计，适合本题规模与 8 MB 内存限制。

出题人解法有两种实现，都利用一次区间投送等于“从 $l$ 开始的后缀贡献”减去“从 $r+1$ 开始的后缀贡献”，因此重叠操作可以先线性叠加。

分块版把贡献位置按块长 $B$ 划分。边界块直接修改，整块先记下后缀起点及次数，最后逐块展开这些记录，再按各投送起点平移累计结果。其时间上界为 $O(q(B+n/B)+n^2+kn+n+m)$ ，存储这些块与偏移计数需要 $O(n^2/B+n+m+k)$ 空间；取 $B$ 约为 $\sqrt n$ .卷积版按后缀起点分组，把物资后缀和带正负号的投送位置计数多项式做 NTT，在变换域累计所有分组，最后统一逆变换。设变换长度为 $H=O(n+m)$ ，出题人实现逐组扫描询问，时间上界为 $O(nq+qk+nH\log H)$ ，空间为 $O(H+n+q+k)$ .模数为 $1004535809$ ；每个输出位置的最终非负答案不超过 $9q\min(n,k)\le9qn$ ，小于该模数，因此最终余数就是整数答案。

Codex（GPT-6）采用的实现保留线性叠加，直接累计有效偏移，然后按投送起点平移，不保存询问、块偏移表或 NTT 工作区。令 $h=\min(n,m)$ ，时间为 $O(n+m+k+qh+kh)$ ，空间为 $O(n+m+k)$ .它适合当前规模与 8 MB 内存限制，实现也较直接；分块法在询问更多时可能减少逐询问工作量，卷积法也有不同适用范围。这是时间与存储的取舍，没有两种实现的直接计时对照。

## 先按偏移合并

所有起点使用完全相同的投送列表，因此先计算单一起点的贡献。令 $s_j$ 表示所有投送在相对起点偏移 $j$ 处提供的补给总量。读入 $[l,r]$ 时，对 $0\le j\le\min(r-l,m-1)$ 执行

$$s_j\gets s_j+a_{l+j}$$

偏移不小于 $m$ 的贡献一定越界，可以略去。随后对每个起点 $p_i$ ，把所有未越界的 $s_j$ 加到答案位置 $p_i+j$ .

## 正确性

题目要求对每个投送、每个起点和每个合法偏移计算一次贡献。算法先固定偏移、对投送求和，再将该和加到各起点对应的位置。交换有限次加法的顺序不改变结果；被略去的偏移在任一起点都会越界。因此每个位置得到的总量恰好符合定义。

## 复杂度与实现

令 $h=\min(n,m)$ .时间复杂度为 $O(n+m+k+qh+kh)$ ，空间复杂度为 $O(n+m+k)$ .本题规模允许直接枚举投送中的有效偏移，无需保存所有询问。参考程序使用固定上限数组，额外数组空间约为 $48$ KB。