题面。
我也想过根号分治，但是题目刷得少，数组不敢开，所以还是看题解做的。
这道题目要用到根号分治的思想，可以看看这道题目和我的题解。
题目要求处理一个数组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;
else
ans=(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;
else
ans=(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;
}
完整代码
总的时间复杂度是m*n1/2，理论上正确。
因为常数因子过大，无法通过本题，进一步提速请看Ynoi2011初始化卡常优化。
标签：
留言评论