80分TLE,update前面是暴力,后面是前缀和维护;BFquery是暴力查询,query是暴力修改的查询,extraquery是差分查询。
#include<stdio.h>
#include<math.h>
const int maxn=200005,mod=1000000007,maxt=505,maxT=105;
int i,j,k,m,n,t,T,marks;
int a[maxn],l[maxt],r[maxt],pos[maxn],sum[maxt],extrasum[maxT],dlv[maxT][maxT],flg[maxT],mark[maxT];
inline void read(int &x){
char c=getchar();
x=0;
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+c-48;
}
inline int mul(int a,int b){
int res=0;
while(b){
if(b&1)
res=(res+a)%mod;
a=(a+a)%mod,b>>=1;
}
return res;
}
void init(){
t=sqrt(n),T=30;
for(i=1;i<=t;i++)
l[i]=r[i-1]+1,r[i]=i*t;
if(r[t]<n)
t++,l[t]=r[t-1]+1,r[t]=n;
for(i=1;i<=t;i++)
for(j=l[i];j<=r[i];j++)
pos[j]=i,sum[i]=(sum[i]+a[j])%mod;
}
void update(int x,int y,int k){
k%=mod;
if(x>T){
for(int i=y%x;i<=n;i+=x)
a[i]=(a[i]+k)%mod,sum[pos[i]]=(sum[pos[i]]+k)%mod;
return ;
}
if(flg[x]==0)
flg[x]=1,mark[++marks]=x;
for(int i=y%x;i<x;i++)
dlv[x][i]=(dlv[x][i]+k)%mod;
extrasum[x]=(extrasum[x]+k)%mod;
}
int BFquery(int x,int y){
int res=0;
for(int i=x;i<=y;i++)
res=(res+a[i])%mod;
return res;
}
int query(int x,int y){
int p=pos[x],q=pos[y],res;
if(p==q)
return BFquery(x,y);
res=(BFquery(x,r[p])+BFquery(l[q],y))%mod;
for(int i=p+1;i<=q-1;i++)
res=(res+sum[i])%mod;
return res;
}
int extraquery(int x,int y){
int res=0;
for(int i=1;i<=marks;i++){
int now=mark[i],l=x+((y-x+1)/now)*now,r=y;
res=(res+mul((y-x+1)/now,extrasum[now]))%mod;
if(l>r)
continue;
l%=now,r%=now;
if(l>r)
res=(res+extrasum[now])%mod;
if(l==0)
res=(res+dlv[now][r])%mod;
else res=(res+dlv[now][r]-dlv[now][l-1])%mod;
}
return res;
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++)
read(a[i]);
init();
for(i=1;i<=m;i++){
int opt,x,y,k;
read(opt);
if(opt==1){
read(x),read(y),read(k);
update(x,y,k);
}
if(opt==2){
read(x),read(y);
printf("%d\n",((query(x,y)+extraquery(x,y))%mod+mod)%mod);
}
}
return 0;
}