수열과 쿼리 13

수열과 쿼리 13

해결

(x, y, z)라는 구간을 2를 더하고 3을 곱하는 작업은 3을 곱하고 6을 더하는 작업과 동일하다.
즉, 순서를 상관없이 처리할 수 있는 점때문에 위 문제를 두가지 lazy변수 2개로 만들어서 해결할 수 있다.

1. lazy[node][0] = 곱해야하는 값 = 1(초기값)
2. lazy[node][1] = 더해야하는 값 = 0(초기값)

곱하고 더해야하는 값을 (m, v)라고 했을 때,
lazy[node][0] *= m;
lazy[node][1] = lazy[node][1] * m + v
tree[node] = tree[node] * lazy[node][0] + (y - x + 1) * tree[node][1] 로 구현할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod = 1e9 + 7;
int n;
ll a[100001], tree[400001], lazy[400001][2];

void init(int node, int x, int y) {
    lazy[node][0] = 1;
    lazy[node][1] = 0;
    if (x == y) {
        tree[node] = a[x];
        return;
    }
    int mid = (x + y) / 2;
    init(node * 2, x, mid);
    init(node * 2 + 1, mid + 1, y);
    tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % mod;
}
void propagation(int node, int x, int y) {
    if (x != y) {
        lazy[node * 2][0] = (lazy[node * 2][0] * lazy[node][0]) % mod;
        lazy[node * 2][1] = (lazy[node * 2][1] * lazy[node][0]) % mod + lazy[node][1];
        lazy[node * 2][1] %= mod;
        lazy[node * 2 + 1][0] = (lazy[node * 2 + 1][0] * lazy[node][0]) % mod;
        lazy[node * 2 + 1][1] = (lazy[node * 2 + 1][1] * lazy[node][0]) % mod + lazy[node][1];
        lazy[node * 2 + 1][1] %= mod;
    }
    tree[node] *= lazy[node][0];
    tree[node] %= mod;
    tree[node] += ((ll)(y - x + 1) * lazy[node][1]) % mod;
    tree[node] %= mod;
    lazy[node][0] = 1;
    lazy[node][1] = 0;
}

void update(int node, int x, int y, int i, int j, int o, int v) {
    propagation(node, x, y);
    if (i > y || j < x) return;
    if (i <= x && y <= j) {
        lazy[node][0] = (lazy[node][0] * o) % mod;
        lazy[node][1] = (lazy[node][1] * o) % mod + v;
        lazy[node][1] %= mod;
        propagation(node, x, y);
        return;
    }
    int mid = (x + y) / 2;
    update(node * 2, x, mid, i, j, o, v);
    update(node * 2 + 1, mid + 1, y, i, j, o, v);
    tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % mod;
}
ll query(int node, int x, int y, int i, int j) {
    propagation(node, x, y);
    if (i > y || j < x) return 0;
    if (i <= x && y <= j) {
        return tree[node];
    }
    int mid = (x + y) / 2;
    return (query(node * 2, x, mid, i, j) + query(node * 2 + 1, mid + 1, y, i, j)) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    init(1, 0, n - 1);
    int m;
    cin >> m;
    while (m--) {
        int x, y, z, k;
        cin >> k >> x >> y;
        if (k == 1) {  // 더하기
            cin >> z;
            update(1, 0, n - 1, x - 1, y - 1, 1, z);
        } else if (k == 2) {  // 곱셈
            cin >> z;
            update(1, 0, n - 1, x - 1, y - 1, z, 0);
        } else if (k == 3) {  // 대입
            cin >> z;
            update(1, 0, n - 1, x - 1, y - 1, 0, z);
        } else {
            cout << query(1, 0, n - 1, x - 1, y - 1) << '\n';
        }
    }
}