Giá trị lớn nhất

Điểm: 0,08 (OI)

Giới hạn thời gian: 0.4s

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~ phép biến đổi, mỗi phép có dạng (~u~, ~v~, ~k~): tăng mỗi phần tử từ vị trí ~u~ đến vị trí ~v~ lên ~k~ đơn vị.

Cho ~p~ câu hỏi, mỗi câu có dạng (~u~, ~v~): cho biết giá trị lớn nhất của các phần tử có vị trí nằm trong đoạn [~u~, ~v~]

Input

Dòng 1: ~n~, ~m~
~m~ dòng tiếp theo, mỗi dòng chứa ~u~, ~v~, ~k~ cho biết một phép biến đổi
Dòng thứ ~m+2~: một số ~p~
~p~ dòng tiếp theo, mỗi dòng chứa 2 số ~u~, ~v~ cho biết một câu hỏi

Output

Gồm ~p~ dòng chứa kết quả tương ứng cho từng câu hỏi.

Giới hạn

~n~, ~m~, ~p~ ~\leq~ ~50000~
~0 < k ~
Giá trị của một phần tử luôn không vượt quá ~2^{31} -1~

Sample Input

Sample Output

Bình luận

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

vominhmanh10 đã bình luận lúc 2, Tháng 12, 2025, 10:42 ← chỉnh sửa →

truy vấn này là sau khi thực hiện toàn bộ cập nhật nên dùng mảng hiệu, tính lại từng phần tử cho sphrase table sẽ dễ hơn

import sys
input = sys.stdin.readline
def solve():
    n, m = map(int, input().split())
    k = 16
    log = [0] * (n + 1)
    for i in range(2, n + 1):
        log[i] = log[i >> 1] + 1
    st = [[0] * n for _ in range(k)]
    a = [0] * (n + 2)
    for _ in range(m):
        l, r, x = map(int, input().split())
        a[l] += x
        a[r + 1] -= x
    for i in range(1, n + 1):
        a[i] += a[i - 1]
        st[0][i - 1] = a[i]
    for i in range(1, k):
        ans = 1 << i
        for j in range(n - ans + 1):
            st[i][j] = st[i - 1][j] if st[i - 1][j] > st[i - 1][j + (ans >> 1)] else st[i - 1][j + (ans >> 1)] 
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        length = r - l + 1
        p = log[length]
        ans = max(st[p][l - 1], st[p][r - (1 << p)])
        print(ans)
solve()

0

vuonghoaitamdz9 đã bình luận lúc 15, Tháng 11, 2025, 8:09

Spoil

Dùng mảng hiệu kết hợp segment tree tìm max

1

ChillzBacon đã bình luận lúc 9, Tháng 8, 2025, 8:43

dùng mảng hiệu + rmq cx qua nhé

-1

vtiendat88 đã bình luận lúc 4, Tháng 1, 2025, 10:14

0.4s python it qua a a

-4

vtiendat88 đã bình luận lúc 4, Tháng 1, 2025, 10:14

def giatrilonnhat(n , m , p): arr = [0] * n for i in m: for id in range(i[0] - 1 , i[1]): arr[id] += i[2] r = [] for j in p: r.append(max(arr[j[0] - 1:j[1]])) return r if name == 'main': n , o = map(int,input().split()) m = [] p = [] for _ in range(o): u = list(map(int,input().split())) m.append(u) k = int(input()) for _ in range(k): v = list(map(int,input().split())) p.append(v) r = giatrilonnhat(n , m , p) for i in r: print(i)

code python thi 0.4s nganws qua admin a

-4

ngthang2022 đã bình luận lúc 30, Tháng 8, 2023, 5:06

prefix sum rồi mói IT có qua được không ạ?

36

leduykhongngu đã bình luận lúc 23, Tháng 5, 2021, 11:53

Đề bài đã được update và time limit đã được giới hạn về 0.4s. Mình đã chấm lại các bài nộp.