Part 1 题解
题意
给出一个长度为
N(≤300000)
的数列
ai
，再给出
M
个询问，每个询问是形如
(x,y)
的形式，你需要输出
ax+ax+y+ax+2y+...+ax+ky
的和，其中
x+(k+1)y>N
。
分析
PS：这道题的做法是对大小进行分块
对于每个询问，首先我们想到的方法是依次将
ax
，
ax+y
，…，
ax+ky
来相加。
但是这样会TLE。
我们应该想一下出现超时的原因，并从这方面加以改进。
超时的原因：
y
可能非常的小，加的次数非常的多。
那么我们可以设一个数
T=H(n)
，即
T
是
n
的一个函数。
对于
y>T
，直接使用上述方法，时间复杂度为
O(n2T)
；
对于
y<T
，要想出另外一种方法。
y
小带来的特殊性就是可以存储下来预处理而不使空间太大。
我们先预处理出
ans[x][y]
表示询问
(x,y)
的答案。
具体的做法是枚举每一个
y
，然后将
x
从大到小枚举递推答案，则有：
ans[x][y]=ans[x+y][y]+a[x]
。
预处理的时间复杂度为
O(nT)
，查询一次的复杂度为
O(1)
。
所以总的时间复杂度为
O(nT+n2T)
。
当
nT=n2T
即
T=n√
时，取得最小值。
所以总的时间复杂度为
O(nn√)
，空间复杂度为
O(nn√)
。
Part 2 变式一
题目
给出一个长度为
N(≤300000)
的数列
ai
，再给出
M
个操作：
① A x d：将
ax
加上
d
；
② Q x y：询问
ax+ax+y+ax+2y+...+ax+ky
的和，其中
x+(k+1)y>N
。
分析
在原题的基础上，只需要对操作①进行维护即可。
对于操作① A x d：
首先将
ax
赋值为
ax+d
。
然后考虑
ax
的改变对于
ans[i][j]
的影响。
我们枚举
j
。
对于相同的
j
，所有
k<i
且
i
与
k
关于
j
同类。都有
ans[k][j]
增大了
d
。
不属于这个类的，统计的时候也不会用到。
那就是——区间增值？
当然可以。
我们对每个
T
开一个树状数组，对于操作A x d，枚举所有的类
1
到
T
，然后将这个类的前
x
位都增大
d
即可。
当
T=n√
时，总的时间复杂度为
O(nn√logn)
。
