离线n*√n做法

先离线操作，把询问的下标存到相应的步长容器中，为了保证容器中下标是有序的，先排个序。对于步长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约等于$\sqrt{2q}$,因此最后时间复杂度就是$O(\sqrt{n}*n)$。1.6*1e8一秒差不多够了。

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int mod = 1e9 + 7;
struct S
{
    int pos, step, id;
};
void sol()
{
    int n, q;
    cin >> n;
    vector<LL> a(n + 1);
    vector<PII> stp[n + 1];
    unordered_set<int> st;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    vector<S> qr(q);
    vector<LL> res(q);
    for (int i = 0; i < q; i++)
    {
        auto &[a, b, c] = qr[i];
        cin >> a >> b;
        c = i;
    }
    sort(qr.begin(), qr.end(), [&](S &a, S &b)
         { return a.pos < b.pos; });
    for (auto [a, b, c] : qr)
    {
        stp[b].push_back({a, c}), st.insert(b);
    }
    vector<LL> s(n + 1), posx(n + 1), sum(n + 1);
    for (int step : st)
    {
        int pos0 = stp[step][0].x;
        vector<int> rst;
        for (auto [pos, id] : stp[step])
        {
            int dpos = (pos - pos0) % step;
            if (sum[dpos])
            {
                if (pos - step >= posx[dpos])
                    res[id] = sum[dpos] - s[pos - step];
                else
                    res[id] = sum[dpos];
                continue;
            }
            posx[dpos] = pos;
            rst.push_back(dpos);
            for (int i = pos; i <= n; i += step)
            {
                if (i == pos)
                    s[i] = a[i];
                else
                    s[i] = s[i - step] + a[i];
                sum[dpos] = s[i];
            }
            if (pos - step >= posx[dpos])
                res[id] = sum[dpos] - s[pos - step];
            else
                res[id] = sum[dpos];
        }
        for (int x : rst)
            sum[x] = 0;
    }
    for (LL x : res)
        cout << x << "\n";
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        sol();
    return 0;
}