let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

GSS - Đoạn con có tổng lớn nhất

solution.md

Đầu tiên xét cách tìm đoạn con có tổng lớn nhất theo tư tưởng chia để trị như sau:

Kí hiệu:

  • \(F[l, r]\) là đoạn con có tổng lớn nhất trên đoạn \([l, r]\) (kết quả của bài toán)
  • \(Sum[l, r]\) là tổng tất cả các phần tử trên đoạn \([l, r]\)
  • \(T[l, r]\) là đoạn con có tổng lớn nhất, bắt đầu từ \(A[l]\)
  • \(S[l, r]\) là đoạn con có tổng lớn nhất, kết thúc tại \(A[r]\)

Ta chia đoạn cần truy vấn \(R\) thành 2 đoạn con \(U, V\), dễ thấy công thức tính:

\[Sum(R) = Sum(U) + Sum(V)\\ T(R) = max \begin{cases} T(U)\\ Sum(U) + T(V)\\ \end{cases}\\ S(R) = max \begin{cases} S(V)\\ Sum(V) + S(U)\\ \end{cases}\\ F(R) = max \begin{cases} F(U)\\ F(V)\\ S(U) + T(V)\\ \end{cases}\]

Trường hợp cơ sở: \(F[i,i] = Sum[i,i] = T[i,i] = S[i,i] = A[i]\)

Cách tính ở trên có độ phức tạp \(O(N\log N)\) cho mỗi truy vấn. Tuy nhiên ta có thể xây dựng một cây phân đoạn (segment tree) để giảm độ phức tạp truy vấn xuống còn \(O(\log N)\).

main.cpp
Open in Github • Download 
#include <vector>
#include <iostream>
using namespace std;

struct value {
    int sum, prefix, postfix, res;
};

value combine(const value &u, const value &v) {
    value r;
    r.sum = u.sum + v.sum;
    r.prefix = max(u.prefix, u.sum + v.prefix);
    r.postfix = max(v.postfix, v.sum + u.postfix);
    r.res = max(u.postfix + v.prefix, max(u.res, v.res));
    return r;
}

struct range {
    int l, r;
    bool inside(const range &b) const {
        return b.l<=l && r<=b.r;
    }
    bool intersect(const range &b) const {
        return !(r<b.l || b.r<l);
    }
};

struct node {
    range r;
    value v;
    node *left, *right;
};

node* build_tree(vector<int> &&a) {
    int n = a.size();

    vector<node *> nodes(n);
    for (int i=0; i<n; i++) {
        nodes[i] = new node {{i,i}, {a[i],a[i],a[i],a[i]}, NULL, NULL};
    }

    while (nodes.size() > 1) {
        vector<node *> tmp;
        int n = nodes.size();
        for (int i=1; i<n; i += 2) {
            node *p = new node {
                {nodes[i-1]->r.l, nodes[i]->r.r},
                combine(nodes[i-1]->v, nodes[i]->v),
                nodes[i-1], nodes[i],
            };
            tmp.push_back(p);
        }
        if (n & 1) tmp.push_back(nodes[n-1]);
        swap(nodes, tmp);
    }
    return nodes[0];
}

value query(const node &p, const range &r) {
    if (p.r.inside(r)) return p.v;
    if (!p.left->r.intersect(r)) return query(*p.right, r);
    if (!p.right->r.intersect(r)) return query(*p.left, r);
    return combine(query(*p.left, r), query(*p.right, r));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    node *root = build_tree(move(a));
    int m; cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << query(*root, {l-1, r-1}).res << '\n';
    }
    return 0;
}
Comments