小清新分块求助

TLE #8 #9 #10

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10,M=710;
int n,m,a[N];
int len,tot,l[N],r[N],bel[N];
int sum[M],ssum[M],add[M];
void init(){
  len=sqrt(n);
  tot=(n-1)/len+1;
  for(int i=1;i<=tot;++i)
    l[i]=r[i-1]+1,r[i]=i*len;
  r[tot]=n;
  for(int i=1;i<=tot;++i){
    for(int j=l[i];j<=r[i];++j) bel[j]=i,sum[i]+=a[j];
    ssum[i]=ssum[i-1]+sum[i];
  }
}
/*void modify(int k,int x){
  sum[bel[k]]+=x; a[k]+=x;
  for(int i=bel[k];i<=tot;++i)
    ssum[i]+=x;
} */
void modify(int x,int y,int w){
  int p=bel[x],q=bel[y];
  if(p==q){
    for(int i=x;i<=y;++i) a[i]+=w,sum[p]+=w;   //sum[i]+=w
    for(int i=p;i<=tot;++i) ssum[i]=ssum[i-1]+sum[i];
    return;
  }
  for(int i=x;i<=r[p];++i)
    a[i]+=w,sum[p]+=w;
  for(int i=p+1;i<=q-1;++i)  //i=p-1
    add[i]+=w,sum[i]+=(r[i]-l[i]+1)*w;
  for(int i=y;i>=l[q];--i) 
    a[i]+=w,sum[q]+=w;
  for(int i=p;i<=tot;++i) 
    ssum[i]=ssum[i-1]+sum[i];
}
int query(int l,int r){
  int p=bel[l],q=bel[r];
  if(p==q) {
    int ans=0;
    for(int i=l;i<=r;++i) ans+=a[i]+add[p];
    return ans;
  }
  int ans=ssum[q-1]-ssum[p+1-1];
  for(int i=l;i<=::r[p];++i) ans+=a[i]+add[p];
  for(int i=r;i>=::l[q];--i) ans+=a[i]+add[q];
  return ans;
}
main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>n>>m;
  for(int i=1;i<=n;++i) cin>>a[i];
  for(int op,l,r,x;m--;){
    cin>>op>>l>>r;
    if(op==1) cin>>x,modify(l,r,x);
    else cout<<query(l,r)<<'\n';
  }
}