【题目标题】热心公主分担宝物

【题目大意】

有 $n$ 个宝物每个宝物都有一个珍稀度 $a_i$ , $m$ 次询问，每次询问给出两个数 $x,y$ ，具体操作为在前x件宝物中选择一个起点 $z$ ，输出 $max( \sum_z^{min(x,z+y-1)} a_i)$ 。

当 $y=1$ 时 $z$ 可以随意取值，当 $y > 1$ 时 $z \% y = 1$ ；对于所有的 $z \in [1,x]$ 。

Subtask:100%

【算法分析】

解法1：

本题采用前缀和、根号分治算法

根号分治我们将把询问中的分为 $y \le \sqrt{n}$ 与 $y > \sqrt{n}$ 两部分,首先我们把所有珍稀度预处理为前缀和形式，来保证以 $O(1)$ 的时间复杂度获得 $\sum_z^{min(x,z+y-1)} a_i$ 。

• $y \le \sqrt{n}$
  对于这一部分我们发现这个 $y$ 的值不会超过 $500$ ，那么我们就可以开个二维数组把所有的 $x,y$ 的情况进行预处理储存起来，查询的时候直接输出即可。
• $y > \sqrt{n}$
  对于这一部分我们发现y的值是大于 $ \sqrt{n} $ 的，这也就使得$z$的可选操作 $(x/y) \le \sqrt{n}$ ,所以我们暴力搜索即可。

时间复杂度为 $O(n \sqrt{n} )$ 。

解法2：

本题原目的是考查根号分治，感谢安阳师范学院物联网 $*$枫提供新的解题思路。

本题采用调和级数解题。

我们可以从1到n预处理，因题目要求 $(y \% i = 0)$ 当我们处理第i个长度时我们只需要预存对所有i的倍数为结尾的数据。而我们每次查询时只需要找到距离x最近的预处理y的值，如果x不为y的倍数我们只需要与上述最近值到x的总和与预处理那个值比较即可。

【参考代码1】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[200005],b[500][200005],n1;
int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);
	cin>>n;
	n1=sqrt(n);
	for (int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for (int i=1;i<=n1;i++){
		ll mx=0,zan=0;
		for (int j=1;j<=n;j++){
			
			zan+=a[j]-a[j-1];
			mx=max(mx,zan);
			b[i][j]=mx;
			if (j%i==0){
				zan=0;
			}
		}
	}
	cin>>m;
	while(m--){
		ll x,y;
		cin>>x>>y;
		if (y<=n1){
			cout<<b[y][x]<<endl;
		}else {
			ll mx=a[x]-a[x-x%y];
			for (int i=y;i<=x;i+=y){
				mx=max(mx,a[i]-a[i-y]);
			}
			cout<<mx<<endl;
		}
	}
}

【参考代码2】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[200005];
vector<ll> e[200005];
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	
	for (int i=1;i<=n;i++){
		e[i].push_back(a[i]);
		for (int j=i+i;j<=n;j+=i){
			e[i].push_back(a[j]-a[j-i]);
			e[i][j/i-1]=max(e[i][j/i-1],e[i][j/i-2]);
		}
	}
	cin>>m;
	while(m--){
		ll x,y;
		cin>>x>>y;
		if (x<y){
			cout<<a[x]<<endl;
		}else {
			ll z=e[y][x/y-1];
			if (z!=x)z=max(z,a[x]-a[x/y*y]);
			cout<<z<<'\n';
		}
	}
}