题解：P13976 数列分块入门 1

· · 题解

可以参考我的分块合集 分块。

#6277. 数列分块入门 1 - 题目 - LibreOJ

题面

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

技巧

区间加法需要一个标记 tag_i 表示块 i 被整体加了多少。散块暴力；整块用 tag。

时间复杂度。设块长为 T，预处理 \mathcal{O}(n)，修改 \mathcal{O}(T+\frac{n}{T})，查询 \mathcal{O}(1)。最优块长为 \sqrt{n}。

代码
#include<bits/stdc++.h>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define tmax(a,b) (a)=max((a),(b))
#define tmin(a,b) (a)=min((a),(b))

using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;

const LL N=3e5+5,M=555;
LL n,a[N],T,tot,be[M],en[M],bel[N],tag[N];

void init(){
    T=tot=sqrt(n);
    for(LL i=1;i<=tot;i++){
        be[i]=en[i-1]+1,en[i]=i*T;
    }
    en[tot]=n;
    for(LL i=1;i<=tot;i++){
        for(LL j=be[i];j<=en[i];j++){
            bel[j]=i;
        }
    }
}
void update(LL l,LL r,LL val){
    if(bel[l]==bel[r]){
        for(LL i=l;i<=r;i++){
            a[i]+=val;
        }
        return;
    }
    for(LL i=l;i<=en[bel[l]];i++){
        a[i]+=val;
    }
    for(LL i=be[bel[r]];i<=r;i++){
        a[i]+=val;
    }
    for(LL i=bel[l]+1;i<=bel[r]-1;i++){
        tag[i]+=val;
    }
}
LL query(LL pos){
    return a[pos]+tag[bel[pos]];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(LL i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(LL i=1,op,l,r,c;i<=n;i++){
        cin>>op>>l>>r>>c;
        if(op){
            cout<<query(r)<<"\n";
        }else{
            update(l,r,c);
        }
    }
    return 0;
}