数列分块入门 7

LibreOJ-6283-数列分块入门 7

分析

• 区间加法
• 区间乘法
• 单点查询

实现

#include <iostream>
#include <cmath>
#define plus PlUs
using namespace std;

const int N = 100010, M = 10007, T = 320;
int n, a[N];
int pos[N], L[T], R[T];
int add[T], mul[T];

void initialize () {
    int t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }

    for (int i = 1; i <= t; ++ i) {
        for (int j = L[i]; j <= R[i]; ++ j)
            pos[j] = i;
        mul[i] = 1;
    }
}
void update (int k) {
    for (int i = L[k]; i <= R[k]; ++ i)
        a[i] = (a[i] * mul[k] + add[k]) % M;
    add[k] = 0, mul[k] = 1;
}
void plus (int l, int r, int val) {
    int x = pos[l], y = pos[r];
    if (x == y) {
        update(x);
        for (int i = l; i <= r; ++ i)
            a[i] = (a[i] + val) % M;
    } else {
        for (int i = x + 1; i <= y - 1; ++ i)
            add[i] = (add[i] + val) % M;
        update(x);
        for (int i = l; i <= R[x]; ++ i)
            a[i] = (a[i] + val) % M;
        update(y);
        for (int i = L[y]; i <= r; ++ i)
            a[i] = (a[i] + val) % M;
    }
}
void multiply (int l, int r, int val) {
    int x = pos[l], y = pos[r];
    if (x == y) {
        update(x);
        for (int i = l; i <= r; ++ i)
            a[i] = (a[i] * val) % M;
    } else {
        for (int i = x + 1; i <= y - 1; ++ i) {
            add[i] = (add[i] * val) % M;
            mul[i] = (mul[i] * val) % M;
        }
        update(x);
        for (int i = l; i <= R[x]; ++ i)
            a[i] = (a[i] * val) % M;
        update(y);
        for (int i = L[y]; i <= r; ++ i)
            a[i] = (a[i] * val) % M;
    }
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    initialize();
    for (int i = 1, opt, l, r, c; i <= n; ++ i) {
        cin >> opt >> l >> r >> c;
        if (opt == 0) {
            plus(l, r, c);
        } else if (opt == 1) {
            multiply(l, r, c);
        } else {
            cout << (a[r] * mul[pos[r]] + add[pos[r]]) % M << endl;
        }
    }
    return 0;
}