题解：P13979 数列分块入门 4

zxh_qwq · 2025-09-12 14:40:38 · 题解

P13979 题解

题意

用分块维护区间加区间查问题。

思路

考虑将序列分为 \sqrt{n} 个块，维护一个 b 数组表示每个块还没有具体加到每个数的值。

当区间加的时候，对每一个散块中的点暴力区间加，对一块整块加到 b 数组上即可。

区间查类似，对于散点答案加上这一个块的标记的值和当前点的值，整块直接用标记乘上块长。

注意，可以所有的都加完后再取模，否则常数会大的过不去。（本人卡了 23 分钟）

代码

#include<bits/stdc++.h>
#pragma optimize(3)
#define int long long
using namespace std;
int n;
int bl=0;
double k=0.5,p=0.5;
int bid[314514],a[314514],b[314514],bls[314514];
void build(int n){
    bl=p*pow(n,k);
    for(int i=1;i<=n;i++){
        bid[i]=(i-1)/bl+1;
        bls[bid[i]]+=a[i];
    }
}
int li(int id){return bl*(id-1)+1;}
int ri(int id){return min(n,bl*id);}
inline void change(int l,int r,int c){
    int t=min(r,ri(bid[l])),f=bid[l];
    for(int i=l;i<=t;i++){
        a[i]+=c;
        bls[f]+=c;
    }
    if(bid[l]!=bid[r]){
        int t=li(bid[r]),f=bid[r];
        for(int i=t;i<=r;i++){
            a[i]+=c;
            bls[f]+=c;
        }
    }
    for(int i=bid[l]+1;i<bid[r];i++)b[i]+=c;
}
inline int query(int l,int r,int modk){
    const int mod=modk;
    int t=ri(bid[l]),f=bid[l];
    int ans=0;
    for(int i=l;i<=min(r,t);i++){
        ans=ans+a[i]+b[f];
    }
    if(bid[l]!=bid[r]){
        int t=li(bid[r]),f=bid[r];
        for(int i=t;i<=r;i++)ans=ans+a[i]+b[f];
    }
    for(int i=bid[l]+1;i<bid[r];i++)ans=ans+b[i]*bl+bls[i];
    return (ans%mod+mod)%mod;
}
main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(n);
    int op,l,r,c;
    for(int i=1;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op==1){
            cout<<query(l,r,c+1)<<"\n";
        }
        else{
            change(l,r,c);
        }
    }
}