【题解】LibreOJ P6277 【数列分块入门1】

背景

既然学了莫队,回来补分块,这应该会成为一个系列。

分析

分块基于“大段维护,边缘暴力”的思想。
我们创建一个加法标记$add[]$,对于每个指令$0\ l\ r\ c$:
1. 若$l$和$r$同时处于第$i$段内,则直接把$A[l$~$r]$都加$c$;
2. 否则,设$l$处于第$p$段,$r$处于第$q$段:
2.1 对于$i\in [p+1,q-1]$,令$add[i]+=d$
2.2 对于开头或结尾不足一整段的两部分,和$1$中相同的方法暴力处理

代码

#include<cstdio>
#include<cmath>
namespace IO{
    inline int read(){
        int ans = 0,op = 1;char s = getchar();
        while(s < '0' || s > '9'){if(s == '-'){op = -1;}s = getchar();}
        while(s >= '0' && s <= '9'){ans = ans * 10 + s - '0';s = getchar();}
        return ans *= op;
    }
    void print(int x){
        if(x < 0) putchar('-'),x = -x;
        if(x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
    void println(int x){
        print(x);putchar('\n');
    }
}
using namespace IO;

const int MAXN = 50000 + 666;
int LEFT[MAXN],RIGHT[MAXN],pos[MAXN],add[MAXN],A[MAXN];

void plus(int l,int r,int d){
    int p = pos[l],q = pos[r];
    if(p == q){for(int i = l;i <= r;i++) A[i] += d;
    }else{
        for(int i = p + 1;i <= q - 1;i++) add[i] += d;
        for(int i = l;i <= RIGHT[p];i++) A[i] += d;
        for(int i = LEFT[q];i <= r;i++) A[i] += d;
    }
}

int main(){
    int n = read();
    for(int i = 1;i <= n;i++) A[i] = read();

    int sqr = sqrt(n);
    for(int i = 1;i <= sqr;i++) LEFT[i] = (i - 1) * sqr + 1,RIGHT[i] = i * sqr;
    if(RIGHT[sqr] < n) sqr++,LEFT[sqr] = RIGHT[sqr - 1] + 1,RIGHT[sqr] = n;
    for(int i = 1;i <= sqr;i++){
        for(int j = LEFT[i];j <= RIGHT[i];j++) pos[j] = i;
    }

    int op,l,r,c;
    while(n--){
        op = read();l = read();r = read();c = read();
        if(op == 0) plus(l,r,c);
        else println(A[r] + add[pos[r]]);
    }

    return 0;
}