Hướng giải của Chmin Đoạn Và 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 cập nhật min đoạn: \(A[i] = \min(A[i], X)\) và truy vấn tổng đoạn. Ta sử dụng cấu trúc Segment Tree Beats:

  • Tại mỗi node quản lý: sum (tổng), mx (giá trị lớn nhất), smx (giá trị lớn thứ nhì, nhỏ hơn mx), và mx_cnt (số lượng phần tử đạt giá trị mx).
  • Khi cập nhật giá trị chmin với \(X\) trên đoạn:
    • Nếu tree[node].mx <= X: dừng lại (không ảnh hưởng).
    • Nếu tree[node].smx < X < tree[node].mx: cập nhật sum -= (mx - X) * mx_cnt, gán mx = X và dừng lại (lúc này chỉ các phần tử lớn nhất bị biến đổi).
    • Ngược lại: đẩy nhãn lười xuống 2 con và đệ quy sâu xuống.

Độ phức tạp trung bình đã được chứng minh là \(O(\log N)\) mỗi thao tác.

Mã nguồn C++ mẫu

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

struct Node {
    long long sum; int mx, smx, mx_cnt;
};

class SegTreeBeats {
    int n; vector<Node> tree;
    void combine(int node) {
        int l = 2*node, r = 2*node+1;
        tree[node].sum = tree[l].sum + tree[r].sum;
        if (tree[l].mx == tree[r].mx) {
            tree[node].mx = tree[l].mx;
            tree[node].mx_cnt = tree[l].mx_cnt + tree[r].mx_cnt;
            tree[node].smx = max(tree[l].smx, tree[r].smx);
        } else if (tree[l].mx > tree[r].mx) {
            tree[node].mx = tree[l].mx;
            tree[node].mx_cnt = tree[l].mx_cnt;
            tree[node].smx = max(tree[l].smx, tree[r].mx);
        } else {
            tree[node].mx = tree[r].mx;
            tree[node].mx_cnt = tree[r].mx_cnt;
            tree[node].smx = max(tree[l].mx, tree[r].smx);
        }
    }
    void push_chmin(int node, int val) {
        if (tree[node].mx <= val) return;
        tree[node].sum -= (long long)(tree[node].mx - val) * tree[node].mx_cnt;
        tree[node].mx = val;
    }
    void push(int node) {
        push_chmin(2*node, tree[node].mx);
        push_chmin(2*node+1, tree[node].mx);
    }
public:
    SegTreeBeats(int size) { n = size; tree.assign(4 * n, {0, -1, -1, 0}); }
    void build(int node, int start, int end, const vector<int>& a) {
        if (start == end) { tree[node] = {(long long)a[start], a[start], -1, 1}; return; }
        int mid = (start + end)/2;
        build(2*node, start, mid, a);
        build(2*node+1, mid+1, end, a);
        combine(node);
    }
    void update_chmin(int node, int start, int end, int l, int r, int val) {
        if (r < start || end < l || tree[node].mx <= val) return;
        if (l <= start && end <= r && tree[node].smx < val) {
            push_chmin(node, val);
            return;
        }
        push(node);
        int mid = (start + end)/2;
        update_chmin(2*node, start, mid, l, r, val);
        update_chmin(2*node+1, mid+1, end, l, r, val);
        combine(node);
    }
    long long query_sum(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node].sum;
        push(node);
        int mid = (start + end)/2;
        return query_sum(2*node, start, mid, l, r) + query_sum(2*node+1, mid+1, end, l, r);
    }
};

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];
    SegTreeBeats st(n);
    st.build(1, 0, n-1, a);
    while (q--) {
        int t, l, r; cin >> t >> l >> r;
        l--; r--;
        if (t == 1) { int x; cin >> x; st.update_chmin(1, 0, n-1, l, r, x); }
        else { cout << st.query_sum(1, 0, n-1, l, r) << "\n"; }
    }
}

Nhận xét

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