rt

感觉非常神奇

#include<bits/stdc++.h>
#define ri register int 
#define ll unsigned long long 
using namespace std;
const int maxn=2e5+7;
const int mod=1e9+7;
int n,m;
int belong[maxn];
int bl[maxn],br[maxn];
ll a[maxn];
ll sum[maxn];
int siz;
ll tag[2003][2003];
ll calc_bg(int l,int r){
	ll ans=0;
	if(r-l<=siz*2){
		for(ri i=l;i<=r;i++){
			ans=ans+a[i];
		}
		return ans;
	}
	for(ri i=l;i<=br[belong[l]];i++)ans=ans+a[i];
	for(ri i=bl[belong[r]];i<=r;i++)ans=ans+a[i];
	for(ri i=belong[l]+1;i<=belong[r]-1;i++){
		ans=ans+sum[i];
	}
	return ans;
}
ll calc_sm(int p,int len){
	return tag[len][n/siz+1]*(p/len)+tag[len][p%len];
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int a){
    if(a<0) putchar('-'),a=-a;
    if(a>=10)write(a/10);
    putchar(a%10+48);
}
signed main(){
	n=read();
	m=read();
	for(ri i=1;i<=n;i++){
		a[i]=read();
	}
	siz=sqrt(n)/4;
	for(ri i=1;i<=n;i++){
		if(i<=siz)belong[i]=1;
		else belong[i]=belong[i-siz]+1;
	}
	memset(bl,0x3f,sizeof(bl));
	for(ri i=1;i<=n;i++){
		bl[belong[i]]=min(bl[belong[i]],i);
		br[belong[i]]=max(br[belong[i]],i);
		sum[belong[i]]+=a[i];
	}
	for(ri i=1;i<=m;i++){
		int op,x,y,z;
		op=read();
		if(op==1){
			y=read();
			x=read();
			z=read();
			if(y>siz){
				for(ri p=x;p<=n;p+=y){
					a[p]=a[p]+z;
					sum[belong[p]]=sum[belong[p]]+z;
				}
			}
			else{
				for(ri p=x;p<=n/siz+1;p++){
					tag[y][p]=tag[y][p]+z;
				}
			}
		}
		else{
			x=read();
			y=read();
			ll ans=calc_bg(x,y);
			for(ri i=1;i<=siz;i++){
				ans=ans+calc_sm(y,i);
				ans=ans-calc_sm(x-1,i);
			}
			write(ans%mod);
			putchar('\n');
		}
	}
	return 0;
}