https://loj.ac/p/6280 区间加区间和

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
using namespace std;
const int N=1e5+10;
int n;ll w[N],len,lt[N];//lt=lazytag
ll id[N],s[N]; 
void add(int l,int r,ll x){
	if(id[l]==id[r]){
		for(int i=l;i<=r;i++) w[i]+=x;
		s[id[l]]+=(ll)(r-l+1)*x;
		return;
	}
	for(int i=l;id[i]==id[l];i++) w[i]+=x,s[id[i]]+=x;
	for(int i=id[l]+1;i<=id[r]-1;i++) lt[i]+=x,s[i]+=len*x;
	for(int i=r;id[i]==id[r];i--) w[i]+=x,s[id[i]]+=x; 
}
ll query(int l,int r,ll p){
	ll ans=0;
	if(id[l]==id[r]){
		for(int i=l;i<=r;i++) ans=(ans+w[i]+lt[id[l]])%p;
		return ans;
	}
	for(int i=l;id[i]==id[l];i++) ans=(ans+w[i]+lt[id[i]])%p;
	for(int i=id[l]+1;i<=id[r]-1;i++) ans=(ans+s[i]+len*lt[i]%p)%p;
	for(int i=r;id[i]==id[r];i--) ans=(ans+w[i]+lt[id[i]])%p;
	return ans;
}
signed main(){
	int opt,l,r;ll c;
	scanf("%d",&n);
	len=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
		id[i]=(i-1)/len+1;
		//当i=sq(n)时候，为第1块
		//不加i-1，i=sq(n)时，为第二块
		s[id[i]]+=w[i]; 
	}
	for(int T=1;T<=n;T++){
		scanf("%d%d%d%lld",&opt,&l,&r,&c);
		if(!opt) add(l,r,c);
		else printf("%lld\n",query(l,r,c+1));
	}
    return 0;   
}