Subarray Sum Queries

Xem PDF



Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng bao gồm \(N\) 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.

Input

  • Dòng đầu tiên gồm hai số nguyên dương \(N, Q\): Kích thước của mảng và số truy vấn.
  • Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^9)\).
  • \(Q\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\)\(x\) \((1 \leq k \leq N, |x| \leq 10^9)\): thay đổi phần tử \(k\) thành giá trị \(x\).

Output

  • 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.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

Test 1

Input
5 3
1 2 -3 5 -1
2 6
3 1
2 -2 
Output
9
13
6

Bình luận

Không có bình luận nào.