题面传送门 不小心抢了个最优解，比第二少了 0.6 s 0.6s 0.6s 分块+根号分治套路题。 看到这种跳着加的就知道是根号分治了。 对于 x > s x>s x>s的直接加，用分块维护。 对于 x < s x<s x<s的，维护数组 f i , j f_{i,j} fi,j表示跳 i i i个，从 j j j开始加了几次。为了之后统计方便，还要前缀和。 统计时，一部分是分块直接统计。另一部分可以在 f i , j f_{i,j} fi,j上算，考虑整块和零散的情况。直接统计前缀和即可。 关于 s s s我取80左右，实测跑得飞快 代码实现:
#include<cstdio> #include<cmath> #define mod 1000000007 using namespace std; int n,m,k,x,y,op,sg; long long q[139][139],fs[1039],ans,a[203009],z; int main(){ // freopen("1.in","r",stdin); register int i,j; scanf("%d%d",&n,&m); sg=70;k=sqrt(n); for(i=1;i<=n;i++)scanf("%lld",&a[i]),fs[i/k]+=a[i]; for(i=1;i<=m;i++){ scanf("%d",&op); if(op==1){ scanf("%d%d%lld",&x,&y,&z); if(x>=sg) for(j=y;j<=n;j+=x) a[j]+=z,fs[j/k]+=z; else { y%=x; for(j=y;j<x;j++) q[x][j]+=z; } } else{ ans=0; scanf("%d%d",&x,&y); if(x/k==y/k)for(j=x;j<=y;j++) ans+=a[j]; else{ for(j=x;j<x/k*k+k;j++) ans+=a[j]; for(j=x/k+1;j<y/k;j++) ans+=fs[j]; for(j=y/k*k;j<=y;j++) ans+=a[j]; } for(j=1;j<=sg;j++){ if(x/j==y/j) ans+=q[j][y%j]-q[j][x%j-1]; else ans+=q[j][j-1]*(y/j-x/j)-q[j][x%j-1]+q[j][y%j]; } printf("%lld\n",ans%mod); } } }