Hướng dẫn giải của [CSES 1190] Subarray Sum Queries

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.

Một lần nữa – chúng ta cần lưu thêm thông tin trong các nút.

Bốn giá trị sau đây là đủ:

  1. ~\texttt{sum}~, tổng các giá trị trong đoạn tương ứng với nút
  2. ~\texttt{max\\_sum}~, tổng đoạn con lớn nhất trong đoạn tương ứng với nút
  3. ~\texttt{max\\_sum\\_left}~, tổng đoạn con lớn nhất bắt đầu từ đầu bên trái của đoạn
  4. ~\texttt{max\\_sum\\_right}~, tổng đoạn con lớn nhất bắt đầu từ đầu bên phải của đoạn

Khi hợp nhất các nút, ta có thể tạo ra các ứng cử viên mới cho tổng đoạn con lớn nhất bằng cách cộng tổng lớn nhất bắt đầu từ đầu bên phải của đoạn của nút con trái với tổng lớn nhất bắt đầu từ đầu bên trái của đoạn của nút con phải.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int TREE_SIZE = 1 << 18;
struct Node {
    ll sum;            // Sum of the values
    ll max_sum;        // Maximum subarray sum
    ll max_sum_left;   // Maximum subarray sum from the left side
    ll max_sum_right;  // Maximum subarray sum from the right side
} tree[TREE_SIZE * 2];

Node merge(Node l, Node r) {
    return {l.sum + r.sum,
            max({l.max_sum, r.max_sum, l.max_sum_right + r.max_sum_left}),
            max(l.max_sum_left, l.sum + r.max_sum_left),
            max(r.max_sum_right, r.sum + l.max_sum_right)};
}

void update(int i, int x) {
    i += TREE_SIZE;
    tree[i] = {x, max(x, 0), max(x, 0), max(x, 0)};
    while (i > 1) {
        i /= 2;
        tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        update(i, x);
    }

    for (int qi = 0; qi < q; ++qi) {
        int k, x;
        cin >> k >> x;
        update(k, x);
        cout << tree[1].max_sum << '\n';
    }
}

Chương trình tham khảo

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int TREE_SIZE = 1 << 18;
struct Node {
    ll sum;            // Sum of the values
    ll max_sum;        // Maximum subarray sum
    ll max_sum_left;   // Maximum subarray sum from the left side
    ll max_sum_right;  // Maximum subarray sum from the right side
} tree[TREE_SIZE * 2];

Node merge(Node l, Node r) {
    return {l.sum + r.sum,
            max({l.max_sum, r.max_sum, l.max_sum_right + r.max_sum_left}),
            max(l.max_sum_left, l.sum + r.max_sum_left),
            max(r.max_sum_right, r.sum + l.max_sum_right)};
}

void update(int i, int x) {
    i += TREE_SIZE;
    tree[i] = {x, max(x, 0), max(x, 0), max(x, 0)};
    while (i > 1) {
        i /= 2;
        tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        update(i, x);
    }

    for (int qi = 0; qi < q; ++qi) {
        int k, x;
        cin >> k >> x;
        update(k, x);
        cout << tree[1].max_sum << '\n';
    }
}

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.