分块爆零求助

KOBE2408 @ 2024-10-11 19:12:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll n,m,st[N],ed[N],p[N],a[N],sum[N],add[N];
void build(){
    ll block=sqrt(n);
    ll t=n/block;
    if(n%block)t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=n;i++){
        p[i]=(i-1)/block+1;
    }
    for(int i=1;i<=t;i++){
        for(int j=st[i];j<=ed[i];j++){
            sum[i]+=a[j];
        }
    }
}
void update(ll l,ll r,ll k){
    ll x=p[l],y=p[r];
    if(x==y){
        for(int i=l;i<=r;i++){
            a[i]+=k;
        }
        sum[x]+=(r-l+1)*k;
    }else{
        for(int i=l+1;i<r-1;i++)add[i]+=k;
        for(int i=l;i<=ed[x];i++)a[i]+=k;
        sum[x]+=k*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)a[i]+=k;
        sum[y]+=k*(r-st[y]+1);
    }
}
void query(ll l,ll r){
    ll x=p[l],y=p[r],ans;
    if(x==y){
        for(int i=l;i<=r;i++){
            ans+=a[i];
        }
        ans+=add[x]*(r-l+1);
    }else{
        for(int i=x+1;i<=y-1;i++)ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
        for(int i=l;i<=ed[x];i++)ans+=a[i];
        ans+=add[x]*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)ans+=a[i];
        ans+=add[y]*(r-st[y]+1);
    }
    cout<<ans-1<<endl;
}
int main(){
    cin>>n>>m;
    memset(add,0,sizeof(add));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build();
    while(m--){
        ll op,l,r,k;
        cin>>op>>l>>r;
        if(op==1){
            cin>>k;
            update(l,r,k);
        }
        else{
            query(l,r);
        }
    }
    return 0;
}

by PRIMITIVE_LIGHTS @ 2024-10-11 19:57:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll n,m,st[N],ed[N],p[N],a[N],sum[N],add[N];
void build(){
    ll block=sqrt(n);
    ll t=n/block;
    if(n%block)t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=t;i++){
        for(int j=st[i];j<=ed[i];j++){
            p[j]=i;
            sum[i]+=a[j];
        }
    }
}
void update(ll l,ll r,ll k){
    ll x=p[l],y=p[r];
    if(x==y){
        for(int i=l;i<=r;i++){
            a[i]+=k;
        }
        sum[x]+=(r-l+1)*k;
    }else{
        for(int i=x+1;i<=y-1;i++)add[i]+=k;
        for(int i=l;i<=ed[x];i++)a[i]+=k;
        sum[x]+=k*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)a[i]+=k;
        sum[y]+=k*(r-st[y]+1);
    }
}
void query(ll l,ll r){
    ll x=p[l],y=p[r],ans=0;
    if(x==y){
        for(int i=l;i<=r;i++){
            ans+=a[i];
        }
        ans+=add[x]*(r-l+1);
    }else{
        for(int i=x+1;i<=y-1;i++)ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
        for(int i=l;i<=ed[x];i++)ans+=a[i];
        ans+=add[x]*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)ans+=a[i];
        ans+=add[y]*(r-st[y]+1);
    }
    cout<<ans<<endl;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build();
    while(m--){
        ll op,l,r,k;
        cin>>op>>l>>r;
        if(op==1){
            cin>>k;
            update(l,r,k);
        }
        else{
            query(l,r);
        }
    }
    return 0;
}

by KOBE2408 @ 2024-10-12 17:37:53

哦哦，谢谢你:-)