分块30pts求条

#include<bits/stdc++.h>
using namespace std;
long long a[100010],k[1010],g[1010],n,q,w,l,r,v,x;
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    x=sqrt(n);
    for(int i=1;i<=x;i++)for(int j=1;j<=x;j++)k[i]+=a[(i-1)*x+j];//加和 
    while(q--){
        scanf("%lld",&w);
        if(w==1){
            scanf("%lld%lld%lld",&l,&r,&v);
            for(int i=l;i<=((l-1)/x+1)*x;i++)a[i]+=v;//暴力加 
            k[(l-1)/x+1]+=v*(((l-1)/x+1)*x-l+1);//加和 
            for(int i=(l-1)/x+2;i<(r-1)/x+1;i++)g[i]+=v;//整块修改
            //同上 
            for(int i=(r-1)/x*x+1;i<=r;i++)a[i]+=v; 
            k[(r-1)/x+1]+=v*(r-((r-1)/x*x+1)+1); 
        }else{
            v=0;
            scanf("%lld%lld",&l,&r);
            if((l-1)/x!=(r-1)/x) {
                for(int i=l;i<=((l-1)/x+1)*x;i++)v+=a[i];//暴力加 
                v+=g[(l-1)/x+1]*(((l-1)/x+1)*x-l+1);//加和 
                for(int i=(l-1)/x+2;i<(r-1)/x+1;i++)v+=k[i]+g[i]*x;//整块求和
                //同上
                for(int i=(r-1)/x*x+1;i<=r;i++)v+=a[i]; 
                v+=g[(r-1)/x+1]*(r-((r-1)/x*x+1)+1); 
            }else for(int i=l;i<=r;i++)v+=a[i];
            printf("%lld\n",v); 
        } 
        for(int i=1;i<=x;i++)printf("%lld %lld\n",k[i],g[i]);
        for(int i=1;i<=n;i++)printf("%lld\n",a[i]); 
    }
}