QMAX2 - Giá trị lớn nhất ver2

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <iostream>
#include <climits>
#include <cstdio>
using namespace std;

const int N = 50000;
int maxValue[4 * N];
int delta[4 * N];

void update(int k, int l, int r, int x, int y, int d) {
    if (l > r || y < l || r < x)
        return;
    if (x <= l && r <= y) {
        maxValue[k] += d;
        delta[k] += d;
    } else {
        update(2 * k + 1, l, (l + r) / 2, x, y, d);
        update(2 * k + 2, (l + r) / 2 + 1, r, x, y, d);
        maxValue[k] = max(maxValue[2 * k + 1], maxValue[2 * k + 2]) + delta[k];
    }
}

int get(int k, int l, int r, int x, int y) {
    if (l > r || y < l || r < x)
        return INT_MIN;
    if (x <= l && r <= y)
        return maxValue[k];
    return max(get(2 * k + 1, l, (l + r) / 2, x, y), get(2 * k + 2, (l + r) / 2 + 1, r, x, y)) + delta[k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int type, x, y;
        cin >> type >> x >> y;
        --x;
        --y;
        if (type == 0) {
            int delta;
            cin >> delta;
            update(0, 0, n - 1, x, y, delta);
        } else {
            printf("%d\n", get(0, 0, n - 1, x, y));
        }
    }
    return 0;
}

Download