题面 。
我也想过根号分治，但是题目刷得少 ， 数组不敢开，所以还是看题解做的 。
【洛谷P5309 Ynoi 2011 初始化 题解】这道题目要用到根号分治的思想，可以看看这道题目和我的题解 。
题目要求处理一个数组a ， 支持如下操作 。
对一个整数x，对数组长度范围内所有位置( y + x * i )加上一个数，y <= x 。
查询区间和
数据范围1e5 ， 使用分块 。
处理修改分块的一大特点就是其已经确定的单次查询复杂度，那么我们可以顺藤摸瓜，以n1/2为分界点推理操作 。
对于x>=n1/2，y + x * i 对应范围内位置不超过n1/2个，可以暴力修改原数组 。
对于x<n1/2，范围内的修改位置过多 ， 但是x是小于n1/2的 。
处理一个辅助数组pre[ i ][ j ]
令modify( x , y )为操作x，y，k加上的值k ， 那么pre[ i ][ j ]表示 modify（i ， 1）+modify（i，2）+...+modify(i，j)
我们修改这个东西，单次操作时间复杂度为n1/2 。
这个操作在处理询问的时候有用 。
处理询问对于一段询问区间l，r 。
先查询其原本的数据和x>=n1/2的修改 ， 这部分已经经过完全修改，可以直接分块求和 。
即对于整块加上整块和，散块暴力求和，时间复杂度n1/2 。
暴力求答案第一部分
if(lb==rb)for(int j=l;j<=r;j++)ans+=a[j],ans%=mod;else{for(int j=l;j<=lb*len;j++)ans+=a[j],ans%=mod;for(int j=lb+1;j<=rb-1;j++)ans+=b_sum[j],ans%=mod;for(int j=(rb-1)*len+1;j<=r;j++)ans+=a[j],ans%=mod;}再查询x<n1/2的修改 。
这时，发现之前求了一个pre[ i ][ j ] 。
对于每个y<=x ， 我们可以求出对应修改（x，y）在l，r内修改的次数 。
文章插图
如图，我们可以发现，l总处于x*k+y1，r总处于x*( k + t )-y2 。
k就是（l-1）/ x，k+t就是 r / x 。
我们可以先求出x在一段长为x的区间内的修改总量，即为modify(x，1)+modify（x，2）+...+modify（x，x)，这东西我们之前求过，就是pre[ x ][ x ]
那么我们可以求出x在x*k~x*(k+t)内的修改总量，即为pre[ x ][ x ] * t。
k是(l-1)/x+1，k+t是
这个修改值还需要减去modify（x，1）+modify（x ， 2）+...+modify（x，y1-1）和 modify（x，y2+1）+modify（x，y2+2）+...+modify（x ， x） 。
即pre[ x ][ y1 ]和pre[ x ][ x ]-pre[ x ][ y2 ] 。
因为这些值都预处理过，所以直接调用，对一个x进行查询的时间复杂度是O(1)，x一共有大约n1/2个 。
这就是分块很有意思的一个地方！预处理和查询操作相互呼应 ， 最终把单次查询时间复杂度拉到n1/2 。
求答案第二部分，x的修改值
for(int j=1;j<len;j++){lb=(l-1)/j+1,rb=(r-1)/j+1;if(lb==rb)ans-=pre[j][(l-1)%j],ans%=mod,ans+=pre[j][(r-1)%j+1],ans%=mod;elseans=(ans+1ll*(rb-lb+1)*pre[j][j]%mod-suf[j][(r-1)%j+2]-pre[j][(l-1)%j])%mod;}于是查这些修改值的时间是n1/2 。
文章插图
文章插图
#include<bits/stdc++.h>using namespace std;const int h=200010;inline int read() {int s = 0, w = 1;char ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-') w= -1;ch = getchar();}while(ch >= '0' && ch <= '9') {s = s * 10 + ch - '0';ch = getchar();}return s * w;}int mod=1e9+7;int n,m;int a[h];int b_sum[h];int len;int pre[2010][2010];int suf[2010][2010];int get_pos(int x){return (x-1)/len+1;}int main(){n=read(),m=read();len=120;for(int i=1;i<=n;i++)a[i]=read(),b_sum[get_pos(i)]+=a[i]%mod,b_sum[get_pos(i)]%=mod;int op,x,y,z;for(int i=1;i<=m;i++){op=read(),x=read(),y=read();if(op==1){z=read();if(x>=len)for(int j=y;j<=n;j+=x)a[j]+=z,a[j]%=mod,b_sum[get_pos(j)]+=z,b_sum[get_pos(j)]%=mod;else{for(int j=y;j<=x;j++)pre[x][j]+=z,pre[x][j]%=mod;for(int j=1;j<=y;j++)suf[x][j]+=z,suf[x][j]%=mod;//这里的suf就是后缀和，suf[x][i]等价于pre[x][x]-pre[x][i-1]}}else{int l=x,r=y,lb=get_pos(x),rb=get_pos(y);int ans=0;if(lb==rb)for(int j=l;j<=r;j++)ans+=a[j],ans%=mod;else{for(int j=l;j<=lb*len;j++)ans+=a[j],ans%=mod;for(int j=lb+1;j<=rb-1;j++)ans+=b_sum[j],ans%=mod;for(int j=(rb-1)*len+1;j<=r;j++)ans+=a[j],ans%=mod;}for(int j=1;j<len;j++){lb=(l-1)/j+1,rb=(r-1)/j+1;if(lb==rb)ans-=pre[j][(l-1)%j],ans%=mod,ans+=pre[j][(r-1)%j+1],ans%=mod;elseans=(ans+1ll*(rb-lb+1)*pre[j][j]%mod-suf[j][(r-1)%j+2]-pre[j][(l-1)%j])%mod;}printf("%d\n",(ans%mod+mod)%mod);}}return 0;}完整代码
