学步园

题意：给一个长度为n的数组，进行p次询问。每次询问输入两个数a,b，输出数组中第a位开始，每隔b位的所有数字之和。(1<=n,p<=3*10^5)

解法：刚看清题意，一直在考虑是不是有什么特殊的数据结构，可以把每次查询的时间复杂度降到O(logn)。但其实仔细分析可以发现如果b>=600，那每次查询最多只需要取500个数字。如果测试数据b都大于600，那么时间复杂度是O(500*p)，可以在限定时间内完成。就是说如果b>=600，我们只需要直接计算就好了。如果b<600，我们可以离线查询。对每一组b相同的查询，我们只需要O(n)的时间就能完成。所以这一步的时间复杂度是O(600*n)。总时间复杂度是O(500*p+600*n)。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#define lint __int64
using namespace std;

const int N = 300005;
const int M = 600;

vector< pair<int, int> > V[M];
int mass[N];
lint sum[N], res[N];

int main() {
    int n, m, a, b, i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", mass + i);
    scanf("%d", &m);
    for (i = 0; i < M; i++) V[i].clear();
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        if (b >= M) {
            res[i] = 0;
            for (j = a; j <= n; j += b)
                res[i] += mass[j];
        } else {
            V[b].push_back(make_pair(i, a));
        }
    }
    for (i = 1; i < M; i++) {
        if (!V[i].empty()) {
            for (j = n; j >= 1; j--) {
                sum[j] = mass[j];
                if (i + j <= n)
                    sum[j] += sum[j+i];
            }
            for (j = 0; j < V[i].size(); j++) {
                res[V[i][j].first] = sum[V[i][j].second];
            }
        }
    }
    for (i = 1; i <= m; i++)
        printf("%I64d\n", res[i]);
    return 0;
}