题解：P13982 数列分块入门 7

Chase12345 · 2025-09-06 23:27:24 · 题解

想必各位对此题都很熟悉，他就是 P3372。所以有两种做法：线段树和分块。

线段树的做法

见此题解。

分块的做法

其实和线段树的懒标记弄的方法几乎没什么区别。

就是还是加乘法标记，然后顺序同上。

仍然是整块和散块的处理。

整块部分：直接标记，记得乘法的时候让加法标记乘上去。加法标记就只需要管加法的部分就行了。

散块部分：直接在原数组处理即可。

然后就是查询部分了。

整块部分和散块部分同理。散块部分暴力加。记得加法的过程中把标记也弄上去。

哎分块题还是太可爱了/ll。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 300005, M = 1005, MOD = 10007;
int n, block_size, blocks;
int a[N], belong[N], l[M], r[M], add[M], mul[M];

void build() {
    block_size = sqrt(n);
    blocks = (n + block_size - 1) / block_size;
    for (int i = 1; i <= blocks; i++) {
        l[i] = (i - 1) * block_size + 1;
        r[i] = min(n, i * block_size);
        mul[i] = 1;
        add[i] = 0;
        for (int j = l[i]; j <= r[i]; j++)
            belong[j] = i;
    }
}

void push_down(int block) {
    for (int i = l[block]; i <= r[block]; i++)
        a[i] = (a[i] * mul[block] + add[block]) % MOD;
    mul[block] = 1;
    add[block] = 0;
}

void update_add(int lft, int rght, int c) {
    int bl = belong[lft], br = belong[rght];
    if (bl == br) {
        push_down(bl);
        for (int i = lft; i <= rght; i++)
            a[i] = (a[i] + c) % MOD;
    } else {
        push_down(bl);
        for (int i = lft; i <= r[bl]; i++)
            a[i] = (a[i] + c) % MOD;
        for (int i = bl + 1; i < br; i++)
            add[i] = (add[i] + c) % MOD;
        push_down(br);
        for (int i = l[br]; i <= rght; i++)
            a[i] = (a[i] + c) % MOD;
    }
}

void update_mul(int lft, int rght, int c) {
    int bl = belong[lft], br = belong[rght];
    if (bl == br) {
        push_down(bl);
        for (int i = lft; i <= rght; i++)
            a[i] = (a[i] * c) % MOD;
    } else {
        push_down(bl);
        for (int i = lft; i <= r[bl]; i++)
            a[i] = (a[i] * c) % MOD;
        for (int i = bl + 1; i < br; i++) {
            mul[i] = (mul[i] * c) % MOD;
            add[i] = (add[i] * c) % MOD;
        }
        push_down(br);
        for (int i = l[br]; i <= rght; i++)
            a[i] = (a[i] * c) % MOD;
    }
}

int query(int pos) {
    int block = belong[pos];
    return (a[pos] * mul[block] + add[block]) % MOD;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= MOD;
    }
    build();
    for (int i = 1; i <= n; i++) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 0)
            update_add(l, r, c % MOD);
        else if (op == 1)
            update_mul(l, r, c % MOD);
        else
            cout << (query(r) % MOD + MOD) % MOD << endl;
    }
    return 0;
}