数列分块入门 1 题解

https://loj.ac/problem/6277

区间加法，单点查询。

分块。

将长为 $n$ 的序列分成 $sqrt{n}$ 块，每块 $sqrt{n}$ 个元素。

每次修改时，中间的整块考虑维护一个 add 标记，周围的整块考虑暴力。

然后就没有然后了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int bel[N],lb[N],rb[N],bl,num,add[N],n,a[N],q;
//bel 表示每个元素在第几块
//lb,rb 为块的左右端点
//add 为加法的标记
void build() {
    bl=sqrt(n),num=n/bl;
    if(n%bl) num++;
    for(int i=1;i<=num;i++)
        lb[i]=(i-1)*bl+1,rb[i]=i*bl;
    rb[num]=n;
    for(int i=1;i<=num;i++)
        for(int j=lb[i];j<=rb[i];j++)
            bel[j]=i;
}
int ask(int l) {
    return a[l]+add[bel[l]];
}
void change(int l,int r,int c) {
    if(bel[l]==bel[r]) {
        for(int i=l;i<=r;i++)
            a[i]+=c;
        return;
    }
    for(int i=l;i<=rb[bel[l]];i++)
        a[i]+=c;
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
        add[i]+=c;
    for(int i=lb[bel[r]];i<=r;i++)
        a[i]+=c;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build();
    for(int i=1;i<=n;i++) {
        int opt,l,r,c;
        scanf("%d %d %d %d",&opt,&l,&r,&c);
        if(opt==1)
            printf("%d
",ask(r));
        else
            change(l,r,c);
    }
}