LibreOJ 6277 数列分块入门 1(分块区修，单点查询)

题目链接

解题思路

  分块模版i

代码

const int maxn = 5e4+10;
int n,sz,num,a[maxn],ls[maxn],rs[maxn],belong[maxn],lazy[maxn];
void build() {
    num = (n+sz-1)/sz; //分块大小
    for (int i = 1; i<=num; ++i) {
        ls[i] = (i-1)*sz+1, rs[i] = i*sz; //每个块左右边界
    }
    rs[num] = n;
    for (int i = 1; i<=n; ++i) belong[i] = (i-1)/sz+1; //每个元素所属块
}
void update(int l, int r, int c) {
    if (belong[l]==belong[r]) { //同一个块直接暴力
        for (int i = l; i<=r; ++i) a[i] += c;
        return;
    }
    //不同块左右暴力，中间块打标记
    for (int i = belong[l]+1; i<belong[r]; ++i) lazy[i] += c;
    for (int i = l; i<=rs[belong[l]]; ++i) a[i] += c;
    for (int i = ls[belong[r]]; i<=r; ++i) a[i] += c;
}
int main() {
    scanf("%d",&n); 
    for (int i = 1; i<=n; ++i) scanf("%d",&a[i]);
    sz = sqrt(n); build();
    for (int i = 1,op,l,r,c; i<=n; ++i) {
        scanf("%d%d%d%d",&op,&l,&r,&c);
        if (!op) update(l,r,c);
        else printf("%d
",a[r]+lazy[belong[r]]);
    }
    return 0;                                                                 
}