Mô tả bài toán: Tìm tổng lớn nhất của dãy con sau mỗi lần cập nhật

Bạn được cung cấp một mảng gồm ~n~ số nguyên. Một số phần tử trong mảng sẽ được cập nhật, và sau mỗi lần cập nhật, bạn cần tìm tổng lớn nhất của một dãy con liên tiếp trong mảng.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: kích thước mảng và số lượng cập nhật.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~: các phần tử ban đầu của mảng.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~k~ và ~x~:
  • ~k~: vị trí của phần tử cần cập nhật (1-based index).
  • ~x~: giá trị mới của phần tử tại vị trí ~k~.

Output:

• Sau mỗi lần cập nhật, in ra tổng lớn nhất của một dãy con liên tiếp trong mảng. Tổng của dãy con rỗng (0 phần tử) được tính là 0.

Ràng buộc:

• ~1 \leq n, m \leq 2 \cdot 10^5~
• ~-10^9 \leq x_i, x \leq 10^9~
• ~1 \leq k \leq n~

Ví dụ:

Input:

5 3
1 2 -3 5 -1
2 6
3 -2
2 2

Output:

9
13

Giải thích:

1. Ban đầu, mảng là [1, 2, -3, 5, -1]. Tổng đoạn con lớn nhất là 9 ([1, 2, -3, 5]).
2. Sau khi cập nhật phần tử thứ 2 thành 6, mảng là [1, 6, -3, 5, -1]. Tổng đoạn con lớn nhất là 13 ([1, 6, -3, 5]).
3. Sau khi cập nhật phần tử thứ 3 thành -2, mảng là [1, 6, -2, 5, -1]. Tổng đoạn con lớn nhất là 13 ([1, 6, -2, 5]).