# SOJ 86. 一維陣列區間加值區間乘值區間查詢總和

Problem Description:
Initially, you are given an array of length N.
Q operations follow:
OP 1: Add C to every element in X..Y
OP 2: Multiply by W on every element in X..Y
OP 3: Output the sum of elements in X..Y, modulo 1e9 + 7

Constraints:
1 ≤ N ≤ 1e6
All values are in int data type range

Solution:
Define the tag as a linear function, thus we need only the slope and intercept to describe, e.g., f(x) = a * x + b. Suppose the current node on segment tree has tag f(x) = a * x + b, and is about to pass it to one of its children with tag g(x) = c * x + d, that child's tag will be changed to a * (c * x + d) + b = (a * c) * x + (a * d + b).

Code:

#include <bits/stdc++.h>

const int MOD = 1e9 + 7;
const int MAXN = 1 << 20;

int N;
int S[MAXN];

int sum[MAXN << 1];
int ta[MAXN << 1], tb[MAXN << 1]; // ax + b

signed main() {
std::ios::sync_with_stdio(false);
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> S[i];
}
std::function<void(int, int, int)> build = [&](int t, int lb, int rb) {
ta[t] = 1;
tb[t] = 0;
if (rb - lb == 1) {
sum[t] = S[lb] % MOD;
return;
}
build(t << 1, lb, lb + rb >> 1);
build(t << 1 | 1, lb + rb >> 1, rb);
sum[t] = (sum[t << 1] + sum[t << 1 | 1]) % MOD;
};
build(1, 0, N);
std::function<void(int, int, int)> push = [&](int t, int lb, int rb) {
int mb = lb + rb >> 1;
sum[t << 1] = (1LL * sum[t << 1] * ta[t] + 1LL * tb[t] * (mb - lb)) % MOD;
sum[t << 1 | 1] = (1LL * sum[t << 1 | 1] * ta[t] + 1LL * tb[t] * (rb - mb)) % MOD;
ta[t << 1] = 1LL * ta[t << 1] * ta[t] % MOD;
ta[t << 1 | 1] = 1LL * ta[t << 1 | 1] * ta[t] % MOD;
tb[t << 1] = (1LL * ta[t] * tb[t << 1] + tb[t]) % MOD;
tb[t << 1 | 1] = (1LL * ta[t] * tb[t << 1 | 1] + tb[t]) % MOD;
ta[t] = 1;
tb[t] = 0;
};
int Q;
std::cin >> Q;
while (Q--) {
int OP;
std::cin >> OP;
if (OP == 1) {
int X, Y, C;
std::cin >> X >> Y >> C;
C %= MOD;
std::function<void(int, int, int, int, int, int)> modify = [&](int t, int lb, int rb, int ql, int qr, int w) {
if (qr <= lb || rb <= ql) return;
if (ql <= lb && rb <= qr) {
sum[t] = (sum[t] + 1LL * w * (rb - lb)) % MOD;
(tb[t] += w) %= MOD;
return;
}
push(t, lb, rb);
modify(t << 1, lb, lb + rb >> 1, ql, qr, w);
modify(t << 1 | 1, lb + rb >> 1, rb, ql, qr, w);
sum[t] = (sum[t << 1] + sum[t << 1 | 1]) % MOD;
};
modify(1, 0, N, X - 1, Y, C);
} else if (OP == 2) {
int X, Y, W;
std::cin >> X >> Y >> W;
W %= MOD;
std::function<void(int, int, int, int, int, int)> modify = [&](int t, int lb, int rb, int ql, int qr, int w) {
if (qr <= lb || rb <= ql) return;
if (ql <= lb && rb <= qr) {
sum[t] = 1LL * sum[t] * w % MOD;
ta[t] = 1LL * ta[t] * w % MOD;
tb[t] = 1LL * tb[t] * w % MOD;
return;
}
push(t, lb, rb);
modify(t << 1, lb, lb + rb >> 1, ql, qr, w);
modify(t << 1 | 1, lb + rb >> 1, rb, ql, qr, w);
sum[t] = (sum[t << 1] + sum[t << 1 | 1]) % MOD;
};
modify(1, 0, N, X - 1, Y, W);
} else {
int X, Y;
std::cin >> X >> Y;
std::function<int(int, int, int, int, int)> query = [&](int t, int lb, int rb, int ql, int qr) {
if (qr <= lb || rb <= ql) return 0;
if (ql <= lb && rb <= qr) return sum[t];
push(t, lb, rb);
return (query(t << 1, lb, lb + rb >> 1, ql, qr) + query(t << 1 | 1, lb + rb >> 1, rb, ql, qr)) % MOD;
};
std::cout << ((query(1, 0, N, X - 1, Y) + MOD) % MOD) << std::endl;
}
}
return 0;
}