p3372

分块做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct kuai{
	int l;int r;int s;int sum;
}k[320];
int lazy[320];
int a[100010],num,sum[100010];
int n,m;
void init(){
	int ll=1,rr=num;
	for(int i=1;i<=num;i++){
		k[i].l=ll;
		k[i].r=rr;
		k[i].s=num;
		for(int j=k[i].l;j<=k[i].r;j++) k[i].sum+=a[j];
		ll=rr+1;
		rr=ll+num-1;
	}
	if(k[num].r!=n){
		k[++num].l=k[num-1].r+1;
		k[num].r=n;
		k[num].s=k[num].r-k[num].l+1;
		for(int j=k[num].l;j<=k[num].r;j++) k[num].sum+=a[j];
	}
}

int find(int x){
	for(int i=1;i<=num;i++){
		if(x>=k[i].l&&x<=k[i].r) return i;
	}
}
void add(int x,int y,int z){
	int l=find(x),r=find(y);
	if (l == r) {
		for (int i = x; i <= y; ++i) {
			a[i] += z;
			k[l].sum += z;
		}
	}
	else {
		for (int i = x; i <= k[l].r; ++i) {
			a[i] += z;
			k[l].sum += z;
		}
		for (int i = k[r].l; i <= y; ++i) {
			a[i] += z;
			k[r].sum += z;
		}
		for(int i=l+1;i<r;i++){
			lazy[i]+=z;
		}
	}
	
}//
void check(int x,int y){
	int ans=0;
	int l=find(x),r=find(y);
	for(int i=x;i<=min(k[l].r, y);i++){  //
		ans+=a[i];
		ans+=lazy[l];
	}
	if(l!=r){
		for(int i=k[r].l;i<=y;i++){ 
		ans+=a[i];
		ans+=lazy[r];
		}
	}
	
	for(int i=l+1;i<r;i++){
		ans+=k[i].sum+k[i].s*lazy[i];
	}
	cout<<ans<<endl;
}
signed main(){
//	freopen("data.txt","r",stdin);
//	freopen("my.txt","w",stdout);
	cin>>n>>m;
	num=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	while(m--){
		int t,x,y,z;
		cin>>t;
		if(t==1){
			cin>>x>>y>>z;
			add(x,y,z);
//			cout<<"Aaaaaa";
//			for(int i=1;i<=n;i++){
//				cout<<a[i]<<" ";
//			}cout<<endl;
//			for(int i=1;i<=num;i++){
//				cout<<lazy[i]<<" ";
//			}cout<<endl;
		}
		else{
			cin>>x>>y;
			check(x,y);
		}
	}
}