Hướng dẫn giải của Truy vấn giá trị lớn nhất trên đoạn


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.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, DragonDP, hai_codeer, nlon0679

Editorial for qlzmax: Truy vấn giá trị lớn nhất trên đoạn

Hiểu bài toán

Bài toán yêu cầu xử lý một dãy số ban đầu gồm n phần tử đều bằng 0. Có m truy vấn cần xử lý, trong đó có hai loại: loại 0 là cập nhật khoảng (cộng d vào các phần tử từ chỉ số u đến v), và loại 1 là truy vấn giá trị lớn nhất trên một khoảng (tìm max các phần tử từ u đến v). Với n, m lên tới 10^5, ta cần một cấu trúc dữ liệu hiệu quả để xử lý cả hai thao tác trong thời gian logarit.

Các cách tiếp cận

Cách Cấu trúc cây phân đoạn (Segment Tree) với Lazy Propagation
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const long long inf = -1e18;

long long t[4 * maxn], lazy[4 * maxn];

// Tải giá trị từ node cha xuống con
void push(int id) {
    if (lazy[id] != 0) {
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        t[id * 2] += lazy[id];
        t[id * 2 + 1] += lazy[id];
        lazy[id] = 0;
    }
}

// Cập nhật giá trị d vào đoạn [u, v]
void update(int id, int l, int r, int u, int v, long long d) {
    if (l > v || r < u) return; // Khoảng không giao nhau

    if (u <= l && r <= v) { // Khoảng bao phủ hoàn toàn
        t[id] += d;
        lazy[id] += d;
        return;
    }

    push(id); // Tải lazy xuống con trước khi đệ quy
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, d);
    update(id * 2 + 1, mid + 1, r, u, v, d);
    t[id] = max(t[id * 2], t[id * 2 + 1]);
}

// Truy vấn giá trị lớn nhất trong đoạn [u, v]
long long query(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return inf; // Khoảng không giao nhau

    if (u <= l && r <= v) return t[id]; // Khoảng bao phủ hoàn toàn

    push(id); // Tải lazy xuống con trước khi đệ quy
    int mid = (l + r) / 2;
    return max(query(id * 2, l, mid, u, v),
               query(id * 2 + 1, mid + 1, r, u, v));
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Khởi tạo cây phân đoạn với giá trị 0
    // Cần gọi build() nếu muốn khởi tạo từ mảng, nhưng ở đây mảng ban đầu toàn 0
    // nên ta có thể xử lý trực tiếp trong update/query
    //memset(t, 0, sizeof(t));
    //memset(lazy, 0, sizeof(lazy));

    while (m--) {
        int type;
        cin >> type;
        if (type == 0) {
            int u, v, d;
            cin >> u >> v >> d;
            update(1, 1, n, u, v, d);
        } else {
            int u, v;
            cin >> u >> v;
            cout << query(1, 1, n, u, v) << '\n';
        }
    }

    return 0;
}
  • Time Complexity: O(m * log n)
  • Space Complexity: O(n)

Đây là cách tiếp cận tối ưu nhất. Cấu trúc cây phân đoạn (Segment Tree) cho phép xử lý các thao tác trên đoạn trong thời gian O(log n). Lazy Propagation là kỹ thuật tối ưu hóa cập nhật khoảng: thay vì cập nhật tất cả các node con mỗi khi sửa đổi một đoạn lớn, ta chỉ đánh dấu (lazy) tại node hiện tại và chỉ cập nhật khi cần thiết (khi truy vấn đi qua node đó hoặc cập nhật chia tách đoạn). Phép cập nhật và truy vấn đều được thực hiện đệ quy, chia đôi khoảng cho đến khi tìm được đoạn bao phủ hoàn toàn hoặc khi gặp đoạn không giao nhau.

Cách Brute Force (Cập nhật trực tiếp)
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
long long a[maxn];

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Khoi tao mang ban dau bang 0
    // Trong C++, mang global se duoc khoi tao mac dinh bang 0

    while (m--) {
        int type;
        cin >> type;
        if (type == 0) {
            int u, v, d;
            cin >> u >> v >> d;
            // Cập nhật trực tiếp từng phần tử trong đoạn [u, v]
            for (int i = u; i <= v; ++i) {
                a[i] += d;
            }
        } else {
            int u, v;
            cin >> u >> v;
            long long max_val = a[u];
            // Tìm max trực tiếp bằng cách duyệt qua các phần tử
            for (int i = u + 1; i <= v; ++i) {
                if (a[i] > max_val) max_val = a[i];
            }
            cout << max_val << '\n';
        }
    }

    return 0;
}
  • Time Complexity: O(m * n)
  • Space Complexity: O(n)

Đây là cách tiếp cận đơn giản nhất nhưng không đủ nhanh cho giới hạn đề bài. Với mỗi truy vấn, ta duyệt qua các phần tử trong đoạn để thực hiện phép cộng hoặc tìm max. Nếu dãy dài 10^5 và có 10^5 truy vấn, độ phức tạp sẽ là 10^10 thao tác, vượt quá giới hạn thời gian cho phép (thường là khoảng 10^8 thao tác/giây). Tuy nhiên, đây là điểm xuất phát tốt để hiểu vấn đề trước khi tối ưu hóa bằng cấu trúc dữ liệu phức tạp hơn.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(m * log n) O(n) Cấu trúc cây phân đoạn (Segment Tree) với Lazy Propagation
2 O(m * n) O(n) Brute Force (Cập nhật trực tiếp)

Bài học kinh nghiệm

  • Khi xử lý các thao tác trên đoạn (range update/range query) trong thời gian thực, Cây phân đoạn (Segment Tree) là cấu trúc dữ liệu phù hợp nhất.
  • Lazy Propagation là kỹ thuật bắt buộc phải dùng khi có cập nhật giá trị trên toàn bộ đoạn lớn, giúp giảm độ phức tạp từ O(n) xuống O(log n) cho mỗi cập nhật.
  • Với bài toán này, cần lưu ý xử lý số nguyên âm (d có thể âm) và số lớn (nên dùng kiểu long long).

Lỗi thường gặp

  • Quên gọi push() trước khi đệ quy vào các node con trong cả hàm update và query, dẫn đến sai lệch giá trị do chưa áp dụng các cập nhật bị hoãn.
  • Lỗi tràn số整数溢出 (overflow) nếu dùng int thay vì long long, đặc biệt khi có nhiều phép cộng dồn.
  • Lỗi index mảng (off-by-one error) khi chuyển từ bài toán 1-indexed (theo đề bài) sang 0-indexed (theo quy ước mảng C++), hoặc ngược lại.

Bình luận

Please read the guidelines before commenting.


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