Giá trị lớn nhất ver2

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 0.5s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy gồm ~n~ phần tử có giá trị ban đầu bằng ~0~.

Cho ~m~ truy vấn có dạng:

  • ~0~ ~x~ ~y~ ~k~: tăng mỗi phần tử từ vị trí ~x~ đến vị trí ~y~ lên ~k~ đơn vị.
  • ~1~ ~x~ ~y~: cho biết giá trị lớn nhất của các phần tử có vị trí nằm trong đoạn [~x~, ~y~]

Input

  • ~n~: số phần tử của dãy ~(n \leq 50000)~.

  • ~m~: số lượng biến đổi và câu hỏi ~(m \le 10^5)~.

    • biến đổi có dạng: ~0~ ~x~ ~y~ ~k~ ~(1 \le k \le 10000)~
    • câu hỏi có dạng: ~1~ ~x~ ~y~

Output

Ghi ra trả lời cho lần lượt từng câu hỏi.

Sample Input

6 3
0 1 3 3
0 4 6 4
1 1 6

Sample Output

4

Bình luận

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


  • 0
    vominhmanh10  đã bình luận lúc 6, Tháng 11, 2025, 4:31 ← chỉnh sửa

    lại lazy

    #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair< ll, ll>;
#define fi first
#define se second
const int maxn = 1e6 + 5;
ll seg[4 * maxn], lazy[4 * maxn];
int n, m;
void down(int node) {
    ll val = lazy[node];
    if (val) {
        lazy[2 * node] += val;
        lazy[2 * node + 1] += val;
        seg[2 * node] += val;
        seg[2 * node + 1] += val;
        lazy[node] = 0;
    }
}

void add(int node, int start, int end, int l, int r, ll val) {
    if (start > r || end < l) return;
    if (start >= l && end <= r) {
        seg[node] += val;
        lazy[node] += val;
        return;
    }
    down(node);
    int mid = (start + end) / 2;
    add(2 * node, start, mid, l, r, val);
    add(2 * node + 1, mid + 1, end, l, r, val);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]);
}

ll query(int node, int start, int end, int l, int r) {
    if (start > r || end < l) return -1e18;
    if (start >= l && end <= r) {
        return seg[node];
        }
        down(node);
    int mid = (start + end) / 2;
    return max(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int t, l, r, k;
    while (cin >> t) {
        if (t) {
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        }
        else {
            cin >> l >> r >> k;
            add(1, 1, n, l, r, k);
        }
    }
}

  • 3
    tuanpham2024  đã bình luận lúc 26, Tháng 6, 2025, 1:43

    Bài này có ai cài bằng Python được không? Dùng Segment Tree Lazy Update cho C++ thì chạy ngon lành mà convert qua Python không sao qua được test cuối (dính TLE).


    • 1
      haoluu2009  đã bình luận lúc 14, Tháng 7, 2025, 14:42

      minh thu cai ben python cung bi TLE a 😭


  • 3
    Anhngutoan  đã bình luận lúc 4, Tháng 2, 2025, 1:07 ← chỉnh sửa

    bruh


  • -6
    huy_lovely  đã bình luận lúc 25, Tháng 7, 2024, 16:29

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    AnonymousExe  đã bình luận lúc 6, Tháng 7, 2024, 14:00

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -57
    PPAP_1264589  đã bình luận lúc 31, Tháng 7, 2021, 13:43 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -34
      nictysine1  đã bình luận lúc 8, Tháng 4, 2022, 0:47

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 21
    leduykhongngu  đã bình luận lúc 22, Tháng 5, 2021, 8:39

    Time limit bài này đã được giảm xuống 0.5s nhé :3