【PBP 0002】数列分块入门 1

题目描述

给出一个长为$n$的数列,以及$n$个操作,操作涉及区间加法,单点查值。
第一行输入一个数字 。

输入格式

第一行输入一个数字 $n$
第二行输入 $n$ 个数字,第$i$个数字为 $a_i$,以空格隔开。
接下来输入 $n$ 行询问,每行输入四个数字 $\mathrm{opt}$、$l$、$r$、$c$,以空格隔开。
若 $opt = 0$,表示将位于 $[l,r]$ 的之间的数字都加 $c$。
若 $opt = 1$,表示询问 $a_r$ 的值( $l$ 和 $c$ 忽略)。

输出格式

对于每次询问,输出一行一个数字表示答案。

样例输入

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

样例输出

2
5

AC Code

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long llint;
const int MAXN = 1e5 + 5;

int n;

struct CHUNK {
    llint a[MAXN], l[MAXN], r[MAXN], m[MAXN], ad[MAXN];
    llint blen, bnum;
    inline void build() {
        memset(a, 0, sizeof(a));
        memset(ad, 0, sizeof(ad));
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        blen = sqrt(n);
        bnum = n/blen;
        if(n % bnum) bnum++;
        for(llint i = 1; i <= bnum; ++i) r[i] = i * blen, l[i] = r[i - 1] + 1;
        r[bnum] = n;
        for(llint i = 1 ; i <= bnum; ++i) {
            for(llint j = l[i]; j <= r[i]; ++j) {
                m[j] = i;
            }
        }
    }
    inline void add(llint from, llint to, llint val) {
        if(m[from] == m[to])
            for(llint i = from; i <= to; ++i) a[i] += val;
        else {
            for(llint i = from; i <= r[m[from]]; ++i) a[i] += val;
            for(llint i = l[m[to]]; i <= to; ++i) a[i] += val;
            for(llint i = m[from] + 1; i < m[to]; ++i) ad[i] += val; 
        }
    }
    inline llint query(int idx) {
        return a[idx] + ad[m[idx]];
    }
} chunk;

int main() {
    scanf("%d", &n);
    chunk.build();
    for(int i = 1; i <= n; ++i) {
        llint opt, l ,r ,c;
        scanf("%lld%lld%lld%lld", &opt, &l ,&r, &c);
        if(!opt) chunk.add(l, r, c);
        else printf("%lld\n", chunk.query(r));
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注