Giá trị lớn nhất ver2

Xem dạng PDF
Gửi bài giải
Điểm: 0,03 (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);
        }
    }
}

  • 2
    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).


    • 0
      vaolu211  đã bình luận lúc 24, Tháng 4, 2026, 1:48 ← sửa 2

      dùng PYPY

      import sys

      def solve():

      input_data = sys.stdin.read().split()
if not input_data:
    return

it = iter(input_data)
out = []

while True:
    try:
        n_str = next(it)
    except StopIteration:
        break

    n_original = int(n_str)
    m = int(next(it))

    n = 1
    while n < n_original:
        n <<= 1

    H = n.bit_length() - 1

    tree = [0] * (2 * n)
    lazy = [0] * (2 * n)

    for _ in range(m):
        type_q = int(next(it))
        if type_q == 0:
            x = int(next(it))
            y = int(next(it))
            k = int(next(it))
            if x > y: x, y = y, x

            l = x - 1 + n
            r = y + n
            l0, r0 = l, r

            for s in range(H, 0, -1):
                i = l >> s
                lz = lazy[i]
                if lz:
                    tree[i << 1] += lz;
                    lazy[i << 1] += lz
                    tree[(i << 1) | 1] += lz;
                    lazy[(i << 1) | 1] += lz
                    lazy[i] = 0

                j = (r - 1) >> s
                if j != i:
                    lz = lazy[j]
                    if lz:
                        tree[j << 1] += lz;
                        lazy[j << 1] += lz
                        tree[(j << 1) | 1] += lz;
                        lazy[(j << 1) | 1] += lz
                        lazy[j] = 0

            while l < r:
                if l & 1:
                    tree[l] += k
                    lazy[l] += k
                    l += 1
                if r & 1:
                    r -= 1
                    tree[r] += k
                    lazy[r] += k
                l >>= 1
                r >>= 1

            p = l0 >> 1
            while p:
                v1 = tree[p << 1];
                v2 = tree[(p << 1) | 1]
                tree[p] = (v1 if v1 > v2 else v2) + lazy[p]
                p >>= 1

            p = (r0 - 1) >> 1
            while p:
                v1 = tree[p << 1];
                v2 = tree[(p << 1) | 1]
                tree[p] = (v1 if v1 > v2 else v2) + lazy[p]
                p >>= 1

        else:
            x = int(next(it))
            y = int(next(it))
            if x > y: x, y = y, x

            l = x - 1 + n
            r = y + n

            for s in range(H, 0, -1):
                i = l >> s
                lz = lazy[i]
                if lz:
                    tree[i << 1] += lz;
                    lazy[i << 1] += lz
                    tree[(i << 1) | 1] += lz;
                    lazy[(i << 1) | 1] += lz
                    lazy[i] = 0

                j = (r - 1) >> s
                if j != i:
                    lz = lazy[j]
                    if lz:
                        tree[j << 1] += lz;
                        lazy[j << 1] += lz
                        tree[(j << 1) | 1] += lz;
                        lazy[(j << 1) | 1] += lz
                        lazy[j] = 0

            res = -10 ** 18
            while l < r:
                if l & 1:
                    if tree[l] > res: res = tree[l]
                    l += 1
                if r & 1:
                    r -= 1
                    if tree[r] > res: res = tree[r]
                l >>= 1
                r >>= 1

            out.append(str(res))

sys.stdout.write("\n".join(out) + "\n")

      if name == 'main': solve()


    • 0
      vaolu211  đã bình luận lúc 24, Tháng 4, 2026, 1:47

      Em giải bằng python được rồi thầy ơiiioiwii 😭


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

      minh thu cai ben python cung bi TLE a 😭


  • 2
    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.


  • -30
    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.


  • -58
    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.


    • -35
      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.


  • 20
    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