分块TLE on #8 #9 #10 help玄关

#include<bits/stdc++.h>
using namespace std;
long long add[100010]; 
long long sum[100010];
long long a[100010];
int pos[100010];
int L[100010],R[100010]; 
void Add(int x,int y,long long k){
    int l=pos[x];
    int r=pos[y];
    if(l==r){
        for(int i=x;i<=y;i++){
            a[i]+=k;
        }
        sum[l]+=(r-l+1)*k;
        return;
    }
    for(int i=l+1;i<=r-1;i++){
        add[i]+=k;
    }
    for(int i=x;i<=R[l];i++){
        a[i]+=k;
    }
    sum[l]+=(R[l]-l+1)*k;
    for(int i=L[r];i<=y;i++){
        a[i]+=k;
    }
    sum[l]+=(r-L[r]+1)*k;
    return;
}
long long Print(int x,int y){
    long long ans=0;
    int l=pos[x];
    int r=pos[y];
    if(l==r){
        for(int i=x;i<=y;i++){
            ans+=a[i];
        }
        ans+=(y-x+1)*add[l];
        return ans;
    }
    for(int i=l+1;i<=r-1;i++){
        ans+=sum[i];
        ans+=(R[i]-L[i]+1)*add[i];
    }
    for(int i=x;i<=R[l];i++){
        ans+=a[i];
    }
    ans+=(R[l]-l+1)*add[l];
    for(int i=L[r];i<=y;i++){
        ans+=a[i];
    }
    ans+=(r-L[r]+1)*add[r];
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    int len=sqrt(n);
    int l=1;
    int id=len;
    for(int i=1;i<=len;i++){
        int r=id+len-1;
        L[i]=l;
        R[i]=r;
        for(int j=l;j<=r;j++){
            sum[i]+=a[j];
            pos[j]=i;   
        }
        l=r+1;
    }
    if(l!=n+1){
        ++id;
        L[id]=l;
        R[id]=n;
        for(int i=l;i<=n;i++){
            sum[id]+=a[i];
            pos[i]=id;
        }
    }
    while(m--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int x,y;
            long long k;
            scanf("%d%d%lld",&x,&y,&k);
            Add(x,y,k);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            long long ans=Print(x,y);
            printf("%lld\n",ans);
        }
    }
    return 0;
}