题解：P13982 数列分块入门 7

xAlec · 2025-09-06 17:02:27 · 题解

Solution

区间乘法，区间加法，单点询问。

其实只需要对每个区间打乘法标记，钦定加法修改的时候先乘后加，乘法修改也要给整块的加法标记乘 c。

复杂度块长取 \sqrt{n} 最小是 O(n\sqrt{n})。

Cpde

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10, MOD = 1e4 + 7;
int n, A[MAXN], blk[MAXN], maxblk, mul[MAXN], add[MAXN], siz, opt, l, r, c;

inline void pushdown (int pos) {
    int l = (pos - 1) * siz + 1, r = min (n, pos * siz);
    for (int i = l; i <= r; i ++)
        A[i] = ((A[i] * mul[pos] % MOD + add[pos]) % MOD + MOD) % MOD;
    mul[pos] = 1, add[pos] = 0;
}
inline void ModifyAdd (int ql, int qr, int c) {
    int lpos = blk[ql], rpos = blk[qr];
    if (lpos == rpos) {
        pushdown (lpos);
        for (int i = ql; i <= qr; i ++) 
            A[i] = ((A[i] + c) % MOD + MOD) % MOD;
    } else {
        for (int i = lpos + 1; i <= rpos - 1; i ++) 
            add[i] = (add[i] + c) % MOD;
        pushdown (lpos), pushdown (rpos);
        for (int i = ql; blk[i] == lpos; i ++) 
            A[i] = ((A[i] + c) % MOD + MOD) % MOD;
        for (int i = qr; blk[i] == rpos; i --) 
            A[i] = ((A[i] + c) % MOD + MOD) % MOD;
    }
}
inline void ModifyMul (int ql, int qr, int c) {
    int lpos = blk[ql], rpos = blk[qr];
    if (lpos == rpos) {
        pushdown (lpos);
        for (int i = ql; i <= qr; i ++)
            A[i] = A[i] * c % MOD;
    } else {
        for (int i = lpos + 1; i <= rpos - 1; i ++) {
            mul[i] = mul[i] * c % MOD;
            add[i] = add[i] * c % MOD;
        }
        pushdown (lpos), pushdown (rpos);
        for (int i = ql; blk[i] == lpos; i ++)
            A[i] = A[i] * c % MOD;
        for (int i = qr; blk[i] == rpos; i --)
            A[i] = A[i] * c % MOD;
    }
}
// function();

signed main() {
    scanf ("%lld", &n), siz = sqrt(n);
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld", &A[i]);
        blk[i] = (i - 1) / siz + 1;
    }
    maxblk = blk[n];
    fill (mul, mul + maxblk + 1, 1);
    // readin();
    for (int i = 1; i <= n; i ++) {
        scanf ("%lld %lld %lld %lld", &opt, &l, &r, &c);
        if (!opt) {
            ModifyAdd (l, r, c);
        } else if (opt == 1) {
            ModifyMul (l, r, c);
        } else {
            printf ("%lld\n", ((A[r] * mul[blk[r]] % MOD + add[blk[r]]) % MOD + MOD) % MOD);
        }
    }
    // output answer
    return 0;
}