Mô tả và yêu cầu

Cho một mảng bao gồm 𝑛 số nguyên. Một số phần tử sẽ được cập nhật, và sau mỗi lần
cập nhật, nhiệm vụ của bạn là tìm tổng lớn nhất của tất cả các đoạn con (liên tiếp)
trong mảng.

Dữ liệu vào: Từ tệp văn bản TONGMAX.INP gồm:
 Dòng đầu tiên gồm hai số nguyên dương 𝑛, 𝑚(1 ≤ 𝑛, 𝑚 ≤ 2 × 105) : Kích
thước của mảng và số truy vấn. Mảng được đánh chỉ số từ 1 đến 𝑛;
 Dòng thứ hai gồm 𝑛 số nguyên 𝑥1, 𝑥2, … ,𝑥𝑛(−109 ≤ 𝑥𝑖 ≤ 109) : giá trị ban
đầu của mảng;
 𝑚 dòng tiếp theo, mỗi dòng có hai số nguyên 𝑘(1 ≤ 𝑘 ≤ 𝑛) và 𝑥(−109 ≤ 𝑥 ≤
109) : thay đổi phần tử ở vị trí 𝑘 thành giá trị 𝑥.
Kết quả: Ghi ra tệp văn bản TONGMAX.OUT gồm:
 Sau mỗi lần cập nhật, in ra tổng lớn nhất của tất cả các đoạn con trong mảng.
Các mảng con rỗng (với tổng bằng 0 ) vẫn được tính.

Ví dụ

TONGMAX.INP             TONGMAX.OUT

                           5                       3

                           1                       9

                           2                       -3

                           3                       -1

                           2                       13

                           2                       6


Ràng buộc:
      Có 40% số lượng test thỏa mãn 𝑛,        𝑚   ≤  100;
      Có 30% số lượng test thỏa mãn 𝑛,         𝑚  ≤  5000;
      Có 30% số lượng test thỏa mãn 𝑛,         𝑚  ≤  2𝑥105.