1422. Range Multiplication @ Caribbean Online Judge.

COJ-1422.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define MOD 1000000009
#define MAX 1000011

long long tree[4 * MAX], lazy[4 * MAX], N, M;

void build(int v, int l, int r) {
    if (l == r) tree[v] = 1;
    else {
        int nL = v << 1, nR = nL + 1, mid = (l + r) / 2;
        build(nL, l, mid);
        build(nR, mid + 1, r);
        tree[v] = (tree[nL] + tree[nR]) % MOD;
    }
}

void push_down(int v, int l, int r) {
    tree[v] = (tree[v] * lazy[v]) % MOD;
    if (l != r) {
        int nL = v << 1, nR = nL + 1;
    	lazy[nL] = (lazy[nL] * lazy[v]) % MOD;
    	lazy[nR] = (lazy[nR] * lazy[v]) % MOD;
    }
    lazy[v] = 1;
}

int query(int v, int l, int r, int i, int j) {
    push_down(v, l, r);
    if (i > r || j < l) return 0;
    if (l >= i && r <= j) return tree[v];
    int nL = v << 1, nR = nL + 1, mid = (l + r) / 2;
    int r1 = query(nL, l, mid, i, j);
    int r2 = query(nR, mid + 1, r, i, j);
    return (r1 + r2) % MOD;
}

long long query(int i, int j) {
    return query(1, 0, N - 1, i, j);
}

void update(int v, int l, int r, int i, int j, int val) {
    push_down(v, l, r);
    if (i > r || j < l) return;
    if (l >= i && r <= j) {
    	lazy[v] = (lazy[v] * val) % MOD;
    	push_down(v, l, r);
    } else {
        int nL = v << 1, nR = nL + 1, mid = (l + r) / 2;
        update(nL, l, mid, i, j, val);
        update(nR, mid + 1, r, i, j, val);
        tree[v] = (tree[nL] + tree[nR]) % MOD;
    }
}

void update(int i, int j, int val) {
    update(1, 0, N - 1, i, j, val);
}

int main() {
    while (cin >> N >> M) {
        for (int i = 0; i <= 4 * N; i++) { lazy[i] = 1; }
        build(1, 0, N - 1);
        for (int i = 0; i < M; i++) {
            int q;
            cin >> q;
            if (q) {
                int x, y;
                cin >> x >> y;
                cout << query(x - 1, y - 1) << endl;
            } else {
                int x, y, k;
                cin >> x >> y >> k;
                update(x - 1, y - 1, k);
            }
        }
    }
}