题解：P13979 数列分块入门 4

Double_Light · 2025-09-07 20:08:21 · 题解

不了解什么是数列分块的同学跳转 P13976。

考虑沿用懒标记的思想，我们维护每个块累计被整体加了多少。对于区间加操作，整块我们更新懒标记，散块直接暴力加。

设块长为 B，则单次修改操作复杂度 O(B+\dfrac nB)。

对于区间求和，散块我们暴力加，整块我们直接用维护的区间和。注意无论散块还是整块都需要加上懒标记。

复杂度为 O(B+\dfrac nB)。

取 B=\sqrt n，总复杂度 O(n\sqrt n)。

代码如下（本题轻微卡常，建议在查询操作过程中不要取模）：

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,B;
struct node{
    int x;
}a[300005];
int minn[300005],maxn[300005],id[300005];
int tag[300005];
int sum[300005];
signed main(){
    cin>>n;
    B=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
        id[i]=(i-1)/B+1;
        sum[id[i]]+=a[i].x;
        minn[i]=(id[i]-1)*B+1;
        maxn[i]=min(n,id[i]*B);
    }
    for(int j=1;j<=n;j++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            for(int i=id[l]+1;i<=id[r]-1;i++)tag[i]+=c;
            for(int i=l;i<=min(r,maxn[l]);i++){
                a[i].x+=c,sum[id[i]]+=c;
            }
            if(id[l]!=id[r]){
                for(int i=max(l,minn[r]);i<=r;i++){
                    a[i].x+=c,sum[id[i]]+=c;
                }
            }
        }
        if(opt==1){
            int ans=0;
            for(int i=id[l]+1;i<=id[r]-1;i++){
                ans+=sum[i]+tag[i]*(maxn[(i-1)*B+1]-minn[(i-1)*B+1]+1);
            }
            for(int i=l;i<=min(r,maxn[l]);i++)ans+=a[i].x+tag[id[i]];
            if(id[l]!=id[r]){
                for(int i=max(l,minn[r]);i<=r;i++)ans+=a[i].x+tag[id[i]]; 
            }
            cout<<(ans%(c+1)+(c+1))%(c+1)<<endl;
        }
    }
    return 0;
}