Truy vấn Tổng Tiền Tố

Điểm: 1,00 (OI)

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

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng $n$ số nguyên. Xử lý $q$ truy vấn:

1 k u — Thay đổi giá trị tại vị trí $k$ thành $u$ .
2 a b — Tìm tổng tiền tố lớn nhất trong đoạn $[a, b]$ , tức là giá trị lớn nhất của $x_{a} + x_{a + 1} + \dots + x_{i}$ với $a \leq i \leq b$ (tiền tố rỗng có tổng bằng 0 cũng được tính).

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng tiền tố lớn nhất.

Input	Output	Giải thích
8 4 1 2 -1 3 1 -5 1 4 2 2 6 1 4 -2 2 2 6 2 3 4	5 2 0	Truy vấn đầu: đoạn [2,6] = [2,-1,3,1,-5], tiền tố lớn nhất = 2+(-1)+3+1 = 5. Sau cập nhật vị trí 4 = -2: đoạn [2,6] = [2,-1,-2,1,-5], tiền tố lớn nhất = 2. Truy vấn cuối: đoạn [3,4] = [-1,-2], tiền tố lớn nhất = 0 (rỗng).

Bình luận

Không có bình luận tại thời điểm này.