先离线操作，把询问的下标存到相应的步长容器中，为了保证容器中下标是有序的，先排个序。对于步长step，那就会存在小于等于step个前缀和，想一想取模运算，其实都差不多。下图就是有三个前缀和，s[1],s[2],s[0]。 思路既然有了那就证明一下时间复杂度，那么对于步长step而言，那就会存在step个前缀和，画个图就明白了，那么遍历一次n/step至少可以更新一个询问操作的答案，那么有q组询问，想一想最坏的情况就是询问的step(就是b)尽可能的小，step等于1的时候遍历一次n,step等于2的时候遍历两次n/2，step等于3的时候遍历三次n/3......以此类推，我们前面说了遍历一次n/step至少可以更新一个询问操作的答案，最坏的情况每次只更新了一个答案，询问次数最坏q=3e5,那我们就要求x，step等于x的时候遍历x次n/x，x约等于2q\sqrt{2q}2q ,因此最后时间复杂度就是O(n∗n)O(\sqrt{n}*n)O(n ∗n)。1.6*1e8一秒差不多够了。

T5 - 前缀和问题 题目链接跳转：点击跳转 > 我个人认为这道题比最后一道题要难，也许是因为这类题目做的比较少的原因，看到题目后不知道从哪下手。 使用分类讨论的方法，设置一个阈值 SSS，考虑暴力枚举所有 b>Sb > Sb>S 的情况，并离线优化 b≤Sb \le Sb≤S 的情况。将 SSS 设置为 N\sqrt{N}N ，则有： 1. 对于大步长 b>Sb > Sb>S，任意一次查询只需要最多遍历 550550550（即 N\sqrt{N}N ）次就可以算出答案，因此暴力枚举这部分。 2. 对于小步长 b≤Sb \le Sb≤S，按 bbb 分组批量离线查询。 对于大步长部分，每一次查询的时间复杂度为 O(N)O(\sqrt{N})O(N )，在最坏情况下总时间复杂度为 O(N×N)O(N \times \sqrt{N})O(N×N )。对于小步长的部分，每一次查询的时间复杂度约为 O(n)O(n)O(n)，在最坏情况下的时间复杂度为 O(N×N)O(N\times \sqrt{N})O(N×N )，因此本题在最坏情况下的渐进时间复杂度为： O(N×N)\large{O(N \times \sqrt{N})} O(N×N ) 最后，本题的 C++ 代码如下： 本题的 Python 代码如下（不保证可以通过所有的测试点）：

想办法把每次询问的运行次数控制在 10310^3103 以内