Giá trị lớn nhất

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 0.4s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
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

6 2
1 3 2
4 6 3
1
3 4

Sample Output

3

Comments

Please read the guidelines before commenting.


  • 0
    vominhmanh10  commented on Dec. 2, 2025, 10:42 a.m. ← edited

    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  commented on Nov. 15, 2025, 8:09 a.m.

    Spoil

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


  • 1
    ChillzBacon  commented on Aug. 9, 2025, 8:43 a.m.

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


  • -1
    vtiendat88  commented on Jan. 4, 2025, 10:14 a.m.

    0.4s python it qua a a


  • -4
    vtiendat88  commented on Jan. 4, 2025, 10:14 a.m.

    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  commented on Aug. 30, 2023, 5:06 a.m.

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


  • 36
    leduykhongngu  commented on May 23, 2021, 11:53 a.m.

    Đề 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.