题解：P13979 数列分块入门 4

Mzh2012 · 2025-09-07 20:05:42 · 题解

分块

分块是一个比较暴力的算法，我们将数据分为一块一块的每块长度是 B，第 i 块的区间和为 s_i。\ 对于每一次对 l 到 r 的查询操作，分为以下两种情况讨论：

1. 如果 l 和 r 在一个区间内，则暴力求解。
2. 如果 l 和 r 不在一个区间内，则暴力求解不完整的块，对于完整的块 i 则直接加上 s_i 即可。最坏的复杂度为 O(\frac{n}{s}+s)。

对于每一次对 l 到 r 的修改操作，也分为两种情况讨论：

1. 如果 l 和 r 在一个区间内，则暴力求解。
2. 如果 l 和 r 不在一个区间内，则暴力求解不完整的块，对于完整的块 i 则直接修改 s_i 即可。最坏的复杂度仍然为 O(\frac{n}{B}+B)。

时间复杂度以及块长

由于总共有 n 次操作，每次操作的复杂度为 O(\frac{n}{B}+B) 所以总共的复杂度为 O(n\cdot(\frac{n}{B}+s))，利用均值不等式可得 \frac{n}{B}+B\le 2\sqrt{n}，当它取等时 B=\sqrt{n}，所以块长取 \sqrt{n} 它的时间复杂度最少，为 O(n\cdot\sqrt{n})。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 5*1e5+1; 
#define int long long
int n,m,a[N],L[N],R[N],id[N],sum[N],tag[N],B;

void build(){
    B = sqrt(n);
    for(int i = 1;i<=n;i++){
        id[i] = (i-1)/B+1; 
        if(!L[id[i]]) L[id[i]] = i;
        R[id[i]] = i;
        sum[id[i]]+=a[i]; 
    }
}

void add(int l,int r,int c){
    int lid = id[l],rid = id[r];
    if(rid==lid){
        for(int i = l;i<=r;i++){
            a[i]+=c;
            sum[id[i]]+=c;
        }
        return;
    }
    for(int i = l;i<=R[lid];i++){//暴力处理不完整的块
        a[i]+=c;
        sum[id[i]]+=c;
    }
    for(int i = L[rid];i<=r;i++){
        a[i]+=c;
        sum[id[i]]+=c;
    }
    for(int i = lid+1;i<rid;i++){
        sum[i]+=(R[i]-L[i]+1)*c;
        tag[i]+=c;
    }
}

int q(int l,int r){
    int lid = id[l],rid = id[r],cnt = 0;
    if(lid==rid){
        for(int i = l;i<=r;i++){
            cnt+=a[i]+tag[id[i]];
        }
        return cnt;
    }
    for(int i = l;i<=R[lid];i++){//暴力处理不完整的块
        cnt+=a[i]+tag[id[i]];
    }
    for(int i = L[rid];i<=r;i++){
        cnt+=a[i]+tag[id[i]];
    }
    for(int i = lid+1;i<=rid-1;i++){
        cnt+=sum[i];
    }
    return cnt;
}

signed main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    build();
    int xx = n;
    while(xx--){
        int opt;
        cin>>opt;
        if(opt==0){
            int l,r,c;
            cin>>l>>r>>c;
            add(l,r,c); 
        }else{
            int l,r,c;
            cin>>l>>r>>c; 
            cout<<(q(l,r)+300000000*(c+1))%(c+1)<<endl;//注意要输出非负数
        }
    }

    return 0;
}