【题目标题】热心公主分担宝物
【题目大意】
有 nnn 个宝物每个宝物都有一个珍稀度 aia_iai , mmm 次询问，每次询问给出两个数 x,yx,yx,y ，具体操作为在前x件宝物中选择一个起点 zzz ，输出 max(∑zmin(x,z+y−1)ai)max( \sum_z^{min(x,z+y-1)} a_i)max(∑zmin(x,z+y−1) ai ) 。
当 y=1y=1y=1 时 zzz 可以随意取值，当 y>1y > 1y>1 时 z%y=1z \% y = 1z%y=1 ；对于所有的 z∈[1,x]z \in [1,x]z∈[1,x] 。
SUBTASK:100%
【算法分析】
解法1：
本题采用前缀和、根号分治算法
根号分治我们将把询问中的分为 y≤ny \le \sqrt{n}y≤n 与 y>ny > \sqrt{n}y>n 两部分,首先我们把所有珍稀度预处理为前缀和形式，来保证以 O(1)O(1)O(1) 的时间复杂度获得 ∑zmin(x,z+y−1)ai\sum_z^{min(x,z+y-1)} a_i∑zmin(x,z+y−1) ai 。
* y≤ny \le \sqrt{n}y≤n
对于这一部分我们发现这个 yyy 的值不会超过 500500500 ，那么我们就可以开个二维数组把所有的 x,yx,yx,y 的情况进行预处理储存起来，查询的时候直接输出即可。
* y>ny > \sqrt{n}y>n
对于这一部分我们发现y的值是大于 $ \sqrt{n} $ 的，这也就使得zzz的可选操作 (x/y)≤n(x/y) \le \sqrt{n}(x/y)≤n ,所以我们暴力搜索即可。
时间复杂度为 O(nn)O(n \sqrt{n} )O(nn ) 。
解法2：
本题原目的是考查根号分治，感谢安阳师范学院物联网 ∗*∗枫提供新的解题思路。
本题采用调和级数解题。
我们可以从1到n预处理，因题目要求 (y%i=0)(y \% i = 0)(y%i=0) 当我们处理第i个长度时我们只需要预存对所有i的倍数为结尾的数据。而我们每次查询时只需要找到距离x最近的预处理y的值，如果x不为y的倍数我们只需要与上述最近值到x的总和与预处理那个值比较即可。
【参考代码1】
【参考代码2】
