分块爆 0 求调

OIer_Hhy @ 2024-10-23 20:17:53

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N];
int L[N],R[N],pos[N],tag[N],val[N],len,cnt;
void build(){
    len=sqrt(n),cnt=(n+len-1)/len;
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*len+1;
        R[i]=min(i*len,n);
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;
            val[i]+=a[j];
        }
    }

}
void update(int l,int r,int k){
    int lpos=pos[l],rpos=pos[r];
    if(lpos==rpos){
        for(int i=l;i<=r;i++) a[i]+=k;
        val[lpos]+=(r-l+1)*k;
        return ;
    }
    for(int i=l;i<=R[lpos];i++) a[i]+=k;
    val[lpos]+=(R[lpos]-l+1)*k;
    for(int i=lpos+1;i<=rpos-1;i++) tag[i]+=k;
    for(int i=L[rpos];i<=r;i++) a[i]+=k;
    val[rpos]+=(r-L[rpos]+1)*k;
}
int query(int l,int r){
    int ans=0;
    int lpos=pos[l],rpos=pos[r];
    if(lpos==rpos){
        for(int i=l;i<=r;i++) ans+=a[i];
        ans+=tag[lpos]*(r-l+1);
        return ans;
    }
    for(int i=l;i<=R[lpos];i++) ans+=a[i];
    ans+=tag[lpos]*(R[lpos]-l+1);
    for(int i=lpos+1;i<=rpos-1;i++) ans+=tag[i]*len;
    for(int i=L[rpos];i<=r;i++) ans+=a[i];
    ans+=tag[rpos]*(r-L[rpos]+1);
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build();
    while(m--){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r,k;
            cin>>l>>r>>k;
            update(l,r,k);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }
    }
    return 0;
}

by JoyLosingK @ 2024-10-23 20:29:58

@OIer_Hhy

改好了，你查询时整块竟然只加上了 tag,还有并不是每个块的长度都为len

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N];
int L[N],R[N],pos[N],tag[N],val[N],len,cnt;
void build(){
    len=sqrt(n),cnt=(n+len-1)/len;
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*len+1;
        R[i]=min(i*len,n);
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;
            val[i]+=a[j];
        }
    }

}
void update(int l,int r,int k){
    int lpos=pos[l],rpos=pos[r];
    if(lpos==rpos){
        for(int i=l;i<=r;i++) a[i]+=k;
        val[lpos]+=(r-l+1)*k;
        return ;
    }
    for(int i=l;i<=R[lpos];i++) a[i]+=k;
    val[lpos]+=(R[lpos]-l+1)*k;
    for(int i=lpos+1;i<=rpos-1;i++) tag[i]+=k;
    for(int i=L[rpos];i<=r;i++) a[i]+=k;
    val[rpos]+=(r-L[rpos]+1)*k;
}
int query(int l,int r){
    int ans=0;
    int lpos=pos[l],rpos=pos[r];
    if(lpos==rpos){
        for(int i=l;i<=r;i++) ans+=a[i];
        ans+=tag[lpos]*(r-l+1);
        return ans;
    }
    for(int i=l;i<=R[lpos];i++) ans+=a[i];
    ans+=tag[lpos]*(R[lpos]-l+1);
    for(int i=lpos+1;i<=rpos-1;i++) ans+=tag[i]*(R[i]-L[i]+1)+val[i];
    for(int i=L[rpos];i<=r;i++) ans+=a[i];
    ans+=tag[rpos]*(r-L[rpos]+1);
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build();
    while(m--){
        int opt;
        cin>>opt;
        if(opt==1){
            int l,r,k;
            cin>>l>>r>>k;
            update(l,r,k);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }
    }
    return 0;
}

by JoyLosingK @ 2024-10-23 20:31:22

@OIer_Hhy 注意第42行，和你原来的比一下

by JoyLosingK @ 2024-10-23 20:31:43

@OIer_Hhy 求关

by OIer_Hhy @ 2024-10-23 20:32:59

@JoyLosingK thx，已关