Hướng dẫn giải của Tăng giá trị đoạn [a,b]

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <bits/stdc++.h> 
#define ll long long
#define fi first
#define se second
#define i2 pair<int,int>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
using namespace std;

const int N = 2e5 + 5; // Kích thước tối đa của mảng
const ll mo = 1e9 + 7;
const int inf = 1e9;
const ll lim = 1e18;

int n, q, a[N]; // n: số phần tử, q: số truy vấn, a[N]: mảng đầu vào

// Cấu trúc dữ liệu của cây phân đoạn
struct SEG {
    ll gt; // Tổng của đoạn quản lý
    ll lz; // Giá trị lazy (để cập nhật đoạn nhanh hơn)
};
SEG t[N * 4]; // Cây phân đoạn (kích thước lớn hơn 4 lần mảng gốc)

// Hàm xây dựng cây phân đoạn (Segment Tree)
void build(int id, int l, int r) {
    if (l == r) { // Nếu là lá, lưu giá trị của phần tử a[l]
        t[id].gt = a[l];
        return;
    }
    int m = (r + l) >> 1; // Chia đôi đoạn
    build(id * 2, l, m); // Xây cây con bên trái
    build(id * 2 + 1, m + 1, r); // Xây cây con bên phải
    t[id].gt = t[id * 2].gt + t[id * 2 + 1].gt; // Gộp kết quả hai con
}

// Hàm đẩy lazy xuống hai con của nút `id`
void push(int id, int l, int r, int m) {
    if (t[id].lz) { // Nếu có giá trị Lazy cần xử lý
        // Cập nhật giá trị tổng của hai con
        t[id * 2].gt += t[id].lz * (m - l + 1); // Con trái (đoạn [l, m])
        t[id * 2 + 1].gt += t[id].lz * (r - m); // Con phải (đoạn [m+1, r])

        // Truyền giá trị Lazy xuống hai con để cập nhật sau
        t[id * 2].lz += t[id].lz;
        t[id * 2 + 1].lz += t[id].lz;

        // Reset Lazy của nút hiện tại sau khi đã đẩy xuống
        t[id].lz = 0;
    }
}

// Hàm cập nhật đoạn [u, v] bằng cách cộng thêm giá trị `x`
void upd(int id, int l, int r, int u, int v, int x) {
    if (u > r || v < l) return; // Nếu ngoài phạm vi, không làm gì

    if (u <= l && v >= r) { // Nếu đoạn [l, r] hoàn toàn nằm trong [u, v]
        t[id].gt += x * (r - l + 1); // Cập nhật tổng của đoạn
        t[id].lz += x; // Đánh dấu lazy để cập nhật sau
        return;
    }

    int m = (r + l) >> 1;
    push(id, l, r, m); // Đẩy Lazy xuống nếu có

    // Gọi đệ quy cập nhật cho hai con
    upd(id * 2, l, m, u, v, x);
    upd(id * 2 + 1, m + 1, r, u, v, x);

    // Cập nhật lại giá trị của nút hiện tại sau khi hai con đã được cập nhật
    t[id].gt = t[id * 2].gt + t[id * 2 + 1].gt;
}

// Hàm truy vấn giá trị tổng trong đoạn [u, v]
ll get(int id, int l, int r, int u, int v) {
    if (u > r || v < l) return 0; // Nếu ngoài phạm vi, trả về 0

    if (u <= l && v >= r) return t[id].gt; // Nếu đoạn nằm hoàn toàn trong phạm vi cần tìm

    int m = (r + l) >> 1;
    push(id, l, r, m); // Đẩy Lazy xuống nếu có

    // Gọi đệ quy tìm tổng của hai con
    return get(id * 2, l, m, u, v) + get(id * 2 + 1, m + 1, r, u, v);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // Đọc dữ liệu từ file (nếu có)
    if (fopen("1.inp", "r")) {
        freopen("1.inp", "r", stdin);
        freopen("1.out", "w", stdout);
    }

    cin >> n >> q; // Nhập số phần tử và số truy vấn
    FOR(i, 1, n) cin >> a[i]; // Nhập mảng đầu vào

    build(1, 1, n); // Xây dựng cây phân đoạn

    while (q--) { // Xử lý q truy vấn
        int ty;
        cin >> ty;

        if (ty == 1) { // Truy vấn loại 1: Cộng `va` vào đoạn [l, r]
            int l, r, va;
            cin >> l >> r >> va;
            upd(1, 1, n, l, r, va);
        } else { // Truy vấn loại 2: Lấy giá trị của phần tử tại vị trí `l`
            int l;
            cin >> l;
            cout << get(1, 1, n, l, l) << '\n';
        }
    }
    return 0;
}


Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.