Truy vấn Tổng Đoạn Con Lớn Nhấ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. Thực hiện $m$ cập nhật, mỗi cập nhật thay đổi một phần tử. Sau mỗi cập nhật, tính tổng lớn nhất của một đoạn con liên tiếp (đoạn rỗng có tổng bằng 0).

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $m$ .
Dòng thứ hai: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .
$m$ dòng tiếp theo: mỗi dòng chứa hai số $k$ và $x$ — gán $x_{k} = x$ .

Dữ liệu ra

Với mỗi cập nhật, in ra một dòng chứa tổng đoạn con lớn nhất.

Ràng buộc

$1 \leq n, m \leq 2 \times 10^{5}$
$- 10^{9} \leq x_{i}, x \leq 10^{9}$
$1 \leq k \leq n$

Ví dụ

Input	Output	Giải thích
5 3 1 2 -3 5 -1 2 6 3 1 2 -2	9 13 6	Sau cập nhật 1: [1,6,-3,5,-1], max subarray = 9 ([1..4]). Sau cập nhật 2: [1,6,1,5,-1], max = 13. Sau cập nhật 3: [1,-2,1,5,-1], max = 6 ([3..4]).
3 2 -1 -2 -3 1 5 2 3	5 8	Sau cập nhật 1: [5,-2,-3], max = 5. Sau cập nhật 2: [5,3,-3], max = 8.

Bình luận

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