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ả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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

Please read the guidelines before commenting.


  • 1
    mducc  đã bình luận lúc 6, Tháng 6, 2026, 11:30 ← chỉnh sửa

    các bạn có thể dùng SegmentTreeLazy để làm bài này

    code tham khảo (C++) 

    #include<bits/stdc++.h> 
#define int long long
using namespace std; 
const int maxn = 1e5 + 2; 
int n, m, que, u, v, d; 
long long st[4 * maxn], lazy[4 * maxn]; 
void push(int id) {
    if(lazy[id]) {
        st[id << 1] += lazy[id]; 
        st[id << 1 | 1] += lazy[id]; 
        lazy[id << 1] += lazy[id]; 
        lazy[id << 1 | 1] += lazy[id]; 
        lazy[id] = 0; 
    }
}
void update(int id, int l, int r, int u, int v, int val) {
    if(r < u || v < l) return; 
    if(u <= l && r <= v) {
        st[id] += val; 
        lazy[id] += val; 
        return;
    }
    push(id); 
    int mid = (l + r) >> 1; 
    update(id << 1, l, mid, u, v, val); 
    update(id << 1 | 1, mid + 1, r, u, v, val); 
    st[id] = max(st[id << 1], st[id << 1 | 1]); 
}
long long query(int id, int l, int r, int u, int v) {
    if(r < u || v < l) return -1e18; 
    if(u <= l && r <= v) return st[id]; 
    push(id); 
    int mid = (l + r) >> 1; 
    return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v)); 
}
int32_t main() {
    ios::sync_with_stdio(true); 
    cin >> n >> m; 
    while(m--) {
        cin >> que >> u >> v; 
        if(que == 0) {
            cin >> d; 
            update(1, 1, n, u, v, d); 
        }
        else cout << query(1, 1, n, u, v) << '\n'; 
    }
}

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

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


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

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