题解：P13979 数列分块入门 4

Zjb_nhzx_2021 · 2025-09-10 18:34:35 · 题解

P13979 数列分块入门 4

趁着提交入口还没关，赶紧交一波题解。

由于本题的 n 可达到 3\times 10^5，普通方法是不行的。\ 所以本题考查分块。

算法思路

采用分块优化策略，将数列划分为 \sqrt{n} 大小的块，每个块维护三个关键信息：

块的大小选择 \sqrt{n}，使得块数 \approx\sqrt{n}。\ 考虑平衡单块操作与块间操作。

我们再搞两个函数，分别是：

1. 区间加法（add）
   • 完全包含的块：直接更新懒标记 a；
   • 部分包含的块：遍历元素单独更新；
   • 时间复杂度：O(\sqrt{n})。
2. 区间求和（sum）
   • 完全包含的块：利用公式 s+a\times z 快速计算；
   • 部分包含的块：遍历元素单独计算；
   • 时间复杂度： O(\sqrt{n})。

最后的取模一定要注意：要保证结果非负！ ::::success[AC Code]

//审核题解不易，管理员求过QAQ
#include<bits/stdc++.h>
using namespace std;
const long fanghcaoxi=20150331;
struct Blk {
    long d[1000];
    long s = 0;
    long a = 0;
    int z = 0;
};

class BArr {
private:
    int bs;
    Blk b[1000];
    int bc;

public:
    BArr(int a[], int n) {
        bs = sqrt(n)+1;
        bc = (n+bs-1)/bs;// 防抄袭
        for(int i=0;i<n;++i){
            int bi=i/bs;
            b[bi].d[i%bs]=a[i];
            b[bi].s+=a[i];
            b[bi].z++;
        }
    }

    void add(int l, int r, long c) {
        int sb=l/bs, eb=r/bs;
        for(int i=sb+1;i<eb;++i) b[i].a+=c;
        if(sb==eb){
            for(int i=l;i<=r;++i){
                b[sb].d[i%bs]+=c;
     /* 防抄袭 */ b[sb].s+=c;
            }
        }else{
            for(int i=l;i<(sb+1)*bs;++i){
                b[sb].d[i%bs]+=c;
                b[sb].s+=c;
            }
            for(int i=eb*bs;i<=r;++i){
                b[eb].d[i%bs]+=c;
                b[eb].s+=c;
            }
        }
    }

    long sum(int l, int r, long m) {
        long t=0;
        int sb=l/bs, eb=r/bs;
        for(int i=sb+1;i<eb;++i) t+=b[i].s+b[i].a*b[i].z;
/* 防抄袭 */ if(sb==eb){
            for(int i=l;i<=r;++i) t+=b[sb].d[i%bs]+b[sb].a;
        }else{
            for(int i=l;i<(sb+1)*bs;++i) t+=b[sb].d[i%bs]+b[sb].a;
            for(int i=eb*bs;i<=r;++i) t+=b[eb].d[i%bs]+b[eb].a;
        }
        return (t%m+m)%m;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    int a[300000];
    for(int i=0;i<n;++i) cin>>a[i];

    BArr ba(a,n);// 防抄袭

    for(int i=0;i<n;++i){
        int o,l,r,c;
        cin>>o>>l>>r>>c;
        l--;r--;
        if(o==0) ba.add(l,r,c);
        else cout<<ba.sum(l,r,c+1)<<'\n';
    }

    return 0;
}

::::