莆田城市投资建设集团网站,开不锈钢公司怎么做网站,直播盒子,浙江省住房和城建建设厅网站一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
103D - Time to Raid Cowavans 二、解题报告
1、思路分析
想了半天数据结构最终选择根号分治
我们考虑 大于 550 的公差直接暴力
小于550 的公差的所有询问#xff0c;我们直接计算该公差后缀和#xf…一、题目
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::pairint, int;
const int inf 1e9 7, P 998244353;void solve() {int n;std::cin n;std::vectori64 w(n);for (int i 0; i n; i ) std::cin w[i];int bound 500;int p;std::cin p;std::vectorstd::vectorPII q(bound);std::vectori64 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::vectori64 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;
}
