[LOJ6280] 数列分块入门 4 - 分块

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，区间求和。

Solution

分为 \(\sqrt n\) 个块，对于每个块，额外维护一个整体加法标记和整体答案

修改时，对于完整的块，需要维护整体加法标记，并更新整体答案；对于零散的块，暴力修改并维护整体答案

询问时，对于完整的块组成的部分，直接给出其整体答案即可；零散的部分暴力统计，注意加上它的整体加法标记

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 50005;

int n,len,b[N],a[N],s[N],t[N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    len=ceil(sqrt(n));
    for(int i=1;i<=n;i++) b[i]=(i-1)/len+1;
    for(int i=1;i<=n;i++) s[b[i]]+=a[i];
    for(int _=1;_<=n;_++) {
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(!opt) {
            if(b[l]==b[r]) {
                for(int i=l;i<=r;i++) a[i]+=c;
                s[b[l]]+=c*(r-l+1);
            }
            else {
                for(int i=b[l]+1;i<b[r];i++) s[i]+=c*len,t[i]+=c;
                s[b[l]]+=(b[l]*len-l+1)*c;
                for(int i=l;i<=b[l]*len;i++) a[i]+=c;
                s[b[r]]+=(r-((b[r]-1)*len+1)+1)*c;
                for(int i=(b[r]-1)*len+1;i<=r;i++) a[i]+=c;
            }
        }
        else {
            int ans=0;
            if(b[l]==b[r]) {
                for(int i=l;i<=r;i++) ans+=a[i]+t[b[i]];
            }
            else {
                for(int i=b[l]+1;i<b[r];i++) ans+=s[i];
                for(int i=l;i<=b[l]*len;i++) ans+=a[i]+t[b[i]];
                for(int i=(b[r]-1)*len+1;i<=r;i++) ans+=a[i]+t[b[i]];
            }
            cout<<ans%(c+1)<<endl;
        }
    }
}

[LOJ6280] 数列分块入门 4 - 分块

原文：https://www.cnblogs.com/mollnn/p/12699372.html