【PB P0003】数列分块入门 4

题目描述

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

输入格式

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

输出格式

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

样例输入

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

样例输出

1
4

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], ad[MAXN], res[MAXN];
    int l[MAXN], r[MAXN], m[MAXN];
    int blen, bnum;
    inline void build() {
        int tmp = 0;
        memset(a, 0, sizeof(a));
        memset(ad, 0, sizeof(ad));
        blen = sqrt(n);
        bnum = n/blen;
        if(n % bnum) bnum++;
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        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) {
                res[i] += a[j];
                m[j] = i;
            }
        }
    }
    inline void add(llint from, llint to, llint val) {
        if(m[from] == m[to])
            for(int i = from; i <= to; ++i) {
                a[i] += val;
                res[m[i]] += val;
            }
        else {
            for(int i = from; i <= r[m[from]]; ++i) {
                a[i] += val;
                res[m[i]] += val;
            }
            for(int i = l[m[to]]; i <= to; ++i) {
                a[i] += val;
                res[m[i]] += val;
            }
            for(int i = m[from] + 1; i < m[to]; ++i) {
                ad[i] += val;
            }
        }
    }
    inline llint query(int from, int to, int val) {
        llint ans = 0;
        if(m[from] == m[to]) {
            for(int i = from; i <= to; ++i) ans = (ans + a[i] + ad[m[i]]) % val;
        }
        else {
            for(int i = from; i <= r[m[from]]; ++i) ans = (ans + a[i] + ad[m[i]]) % val;
            for(int i = m[from] + 1; i < m[to]; ++i) ans = (ans + res[i] + blen * ad[i]) % val;
            for(int i = l[m[to]]; i <= to; ++i) ans = (ans + a[i] + ad[m[i]]) % val;
        }
        return ans % val;
    }
} chunk;

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

发表评论

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