世纪轰炸机：题解¶
解法比较¶
分块、卷积和直接累计适用于不同的参数范围，作为并列方案。标程采用直接累计，适合本题规模与 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)\) 执行
偏移不小于 \(m\) 的贡献一定越界，可以略去。随后对每个起点 \(p_i\) ，把所有未越界的 \(s_j\) 加到答案位置 \(p_i+j\) .
正确性¶
题目要求对每个投送、每个起点和每个合法偏移计算一次贡献。算法先固定偏移、对投送求和，再将该和加到各起点对应的位置。交换有限次加法的顺序不改变结果；被略去的偏移在任一起点都会越界。因此每个位置得到的总量恰好符合定义。
复杂度与实现¶
令 \(h=\min(n,m)\) .时间复杂度为 \(O(n+m+k+qh+kh)\) ，空间复杂度为 \(O(n+m+k)\) .本题规模允许直接枚举投送中的有效偏移，无需保存所有询问。参考程序使用固定上限数组，额外数组空间约为 \(48\) KB。