哏号分治，CF103D - Time to Raid Cowavans

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

103D - Time to Raid Cowavans

---

二、解题报告

1、思路分析

想了半天数据结构最终选择根号分治

我们考虑 大于 550 的公差直接暴力

小于550 的公差的所有询问，我们直接计算该公差后缀和，对于该公差所有询问统一处理

2、复杂度

时间复杂度： O()空间复杂度：O()

3、代码详解

 ​

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
using PII = std::pair<int, int>;
const int inf = 1e9 + 7, P = 998244353;void solve() {int n;std::cin >> n;std::vector<i64> w(n);for (int i = 0; i < n; i ++ ) std::cin >> w[i];int bound = 500;int p;std::cin >> p;std::vector<std::vector<PII>> q(bound);std::vector<i64> ans(p);for (int i = 0, a, b; i < p; i ++ ) {std::cin >> a >> b;-- a;if (b >= bound) {i64& s = ans[i];for (int j = a; j < n; j += b)s += w[j];}elseq[b].push_back( { a, i } );}for (int i = 1; i < bound; i ++ ) {if (q[i].size()) {std::vector<i64> acc(n + i);for (int j = n - 1; j >= 0; j -- ) {acc[j] = acc[j + i] + w[j];}std::cout << '\n';for (auto [j, id] : q[i])ans[id] = acc[j];}}for (i64 x : ans) std::cout << x << '\n';
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}