Hướng giải của Cộng Nhân Đoạn Tính Tổng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán quản lý đồng thời 2 loại nhãn lười: Nhân (mul_lazy) và Cộng (add_lazy). Khi áp dụng một phép nhân với \(M\) và cộng thêm \(A\) lên một nút quản lý đoạn:

  • Giá trị tổng mới: sum = (sum * M + A * len) % MOD.
  • Để tính toán đúng khi đẩy nhãn lười xuống con, ta thiết lập mối quan hệ lồng nhau:
    • Phép nhân có độ ưu tiên cao hơn. Nhãn lười của các nút con sẽ biến đổi như sau khi nhận thêm nhãn (mul, add) từ cha:
      • child.mul_lazy = (child.mul_lazy * mul) % MOD.
      • child.add_lazy = (child.add_lazy * mul + add) % MOD.

Độ phức tạp thời gian: \(O(\log N)\) mỗi truy vấn.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

struct Node {
    long long sum, mul_lazy, add_lazy;
};

struct SegTree {
    int n; vector<Node> tree;
    SegTree(int size) {
        n = size;
        tree.assign(4 * n, {0, 1, 0});
    }
    void build(int node, int start, int end, const vector<int>& a) {
        if (start == end) { tree[node].sum = a[start] % MOD; return; }
        int mid = (start + end)/2;
        build(2*node, start, mid, a);
        build(2*node+1, mid+1, end, a);
        tree[node].sum = (tree[2*node].sum + tree[2*node+1].sum) % MOD;
    }
    void push(int node, int start, int end) {
        long long mul = tree[node].mul_lazy;
        long long add = tree[node].add_lazy;
        if (mul == 1 && add == 0) return;

        tree[node].sum = (tree[node].sum * mul + add * (end - start + 1)) % MOD;
        if (start != end) {
            for (int child : {2*node, 2*node+1}) {
                tree[child].mul_lazy = (tree[child].mul_lazy * mul) % MOD;
                tree[child].add_lazy = (tree[child].add_lazy * mul + add) % MOD;
            }
        }
        tree[node].mul_lazy = 1;
        tree[node].add_lazy = 0;
    }
    void update(int node, int start, int end, int l, int r, long long mul, long long add) {
        push(node, start, end);
        if (r < start || end < l) return;
        if (l <= start && end <= r) {
            tree[node].mul_lazy = mul;
            tree[node].add_lazy = add;
            push(node, start, end);
            return;
        }
        int mid = (start + end)/2;
        update(2*node, start, mid, l, r, mul, add);
        update(2*node+1, mid+1, end, l, r, mul, add);
        tree[node].sum = (tree[2*node].sum + tree[2*node+1].sum) % MOD;
    }
    long long query(int node, int start, int end, int l, int r) {
        push(node, start, end);
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node].sum;
        int mid = (start + end)/2;
        return (query(2*node, start, mid, l, r) + query(2*node+1, mid+1, end, l, r)) % MOD;
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; if (!(cin >> n >> q)) return 0;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    SegTree st(n);
    st.build(1, 0, n-1, a);
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        l--; r--;
        if (t == 1) { long long v; cin >> v; st.update(1, 0, n-1, l, r, v, 0); }
        else if (t == 2) { long long v; cin >> v; st.update(1, 0, n-1, l, r, 1, v); }
        else { cout << st.query(1, 0, n-1, l, r) << "\n"; }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.