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;
}