SCUT - 37 - 手速帝CZK

一开始想到要根号分块预处理，但是不太懂具体怎么写。想不到如此暴力。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 300000;

//预留长出来的600

ll a[MAXN + 800 + 5];

ll res[MAXN + 800 + 5];

ll ans[MAXN + 800 + 5];

struct Query {

    int x, y, id;

} q;

vector<Query>v[800 + 5];

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; ++i)

        scanf("%lld", &a[i]);

    int block = (int)sqrt(n) + 200;

    for(int i = 1, x, y; i <= m; ++i) {

        scanf("%d%d", &x, &y);

        if(y > block) {

            //长度比较长，直接暴力统计

            for(int j = x; j <= n; j += y)

                ans[i] += a[j];

        } else {

            q.x = x, q.y = y, q.id = i;

            v[y].push_back(q);

        }

    }

    for(int y = block; y >= 1; --y) {

        for(int i = n; i >= 0; --i) {

            //暴力统计后缀和

            res[i] = a[i] + res[i + y];

        }

        int len = v[y].size();

        for(int i = 0; i < len; ++i)

            ans[v[y][i].id] = res[v[y][i].x];

    }

    for(int i = 1; i <= m; ++i)

        printf("%lld\n", ans[i]);

}

巴特西

SCUT - 37 - 手速帝CZK - 分块

最新文章

热门文章