QLZMAX - Truy vấn giá trị lớn nhất trên đoạn

Xem dạng PDF
Gửi bài giải
Điểm: 3,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho dãy ~n~ số nguyên ~a_1, a_2, …, a_n~, ban đầu tất cả đều bằng ~0~.Cho ~m~ truy vấn, mỗi truy vấn có một trong hai dạng:

  • ~0\ u\ v\ d:~ cộng giá trị ~d~ vào các phần tử ~a_u, a_{u + 1}, …, a_v~;
  • ~1\ u\ v:~ Tìm giá trị lớn nhất của dãy con ~a_u, a_{u + 1}, …, a_v~.

Input

  • Dòng đầu chứa hai số nguyên dương ~n, m~;
  • ~m~ dòng sau, mỗi dòng chứa một truy vấn (thuộc một trong hai loại trên).

Giới hạn:

  • ~1 ≤ n, m ≤ 10^5; 1 ≤ u ≤ v ≤ n; |d| ≤ 1000~.

Output

  • Với mỗi truy vấn loại hai, ghi ra trên một dòng đáp án của truy vấn đó.

Sample

Input #1
6 3
0 1 3 3
0 4 6 4
1 1 6
Output #1
4

Hint

  • Dãy ban đầu: ~0, 0, 0, 0, 0, 0~;
  • Dãy sau truy vấn thứ nhất: ~3, 3, 3, 0, 0, 0~;
  • Dãy sau truy vấn thứ hai: ~3, 3, 3, 4, 4, 4~;
  • Đáp số của truy vấn thứ ba: ~4~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    lephuochauhungvuong  đã bình luận lúc 11, Tháng 3, 2025, 7:34 ← sửa 3 
    #include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // Thêm header này

using namespace std;

struct Node {
    int maxVal;
    int lazy;
};

void buildTree(vector<int>& arr, vector<Node>& tree, int node, int start, int end) {
    if (start == end) {
        tree[node].maxVal = arr[start];
        tree[node].lazy = 0;
        return;
    }
    int mid = (start + end) / 2;
    buildTree(arr, tree, 2 * node + 1, start, mid);
    buildTree(arr, tree, 2 * node + 2, mid + 1, end);
    tree[node].maxVal = max(tree[2 * node + 1].maxVal, tree[2 * node + 2].maxVal);
    tree[node].lazy = 0;
}

void pushDown(vector<Node>& tree, int node) {
    if (tree[node].lazy != 0) {
        tree[2 * node + 1].maxVal += tree[node].lazy;
        tree[2 * node + 2].maxVal += tree[node].lazy;
        tree[2 * node + 1].lazy += tree[node].lazy;
        tree[2 * node + 2].lazy += tree[node].lazy;
        tree[node].lazy = 0;
    }
}

void updateRange(vector<Node>& tree, int node, int start, int end, int left, int right, int val) {
    if (left > end || right < start) {
        return;
    }
    if (left <= start && end <= right) {
        tree[node].maxVal += val;
        tree[node].lazy += val;
        return;
    }
    pushDown(tree, node);
    int mid = (start + end) / 2;
    updateRange(tree, 2 * node + 1, start, mid, left, right, val);
    updateRange(tree, 2 * node + 2, mid + 1, end, left, right, val);
    tree[node].maxVal = max(tree[2 * node + 1].maxVal, tree[2 * node + 2].maxVal);
}

int queryMax(vector<Node>& tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return INT_MIN; // Đã thêm include <climits> nên INT_MIN được định nghĩa
    }
    if (left <= start && end <= right) {
        return tree[node].maxVal;
    }
    pushDown(tree, node);
    int mid = (start + end) / 2;
    return max(queryMax(tree, 2 * node + 1, start, mid, left, right),
               queryMax(tree, 2 * node + 2, mid + 1, end, left, right));
}

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

    vector<int> arr(n, 0);
    vector<Node> tree(4 * n);

    buildTree(arr, tree, 0, 0, n - 1);

    for (int i = 0; i < m; ++i) {
        int type, u, v, d;
        cin >> type;

        if (type == 0) {
            cin >> u >> v >> d;
            updateRange(tree, 0, 0, n - 1, u - 1, v - 1, d);
        } else if (type == 1) {
            cin >> u >> v;
            cout << queryMax(tree, 0, 0, n - 1, u - 1, v - 1) << endl;
        }
    }

    return 0;
}

  • -1
    tuandat59  đã bình luận lúc 8, Tháng 2, 2025, 1:26

    help ai cho xin ý tưởng vs bí quá


  • -1
    DuckYB  đã bình luận lúc 30, Tháng 5, 2024, 8:09

    gửi code xong nó bị sao vậy mn?