Cho một dãy số gồm phần tử. Bạn cần cắt dãy thành các đoạn sao cho tổng giá trị các đoạn là lớn nhất.
Giá trị của một đoạn = (phần tử lớn nhất) – (phần tử nhỏ nhất) trong đoạn.
Có truy vấn, mỗi truy vấn tăng giá trị các phần tử từ chỉ số đến lên đơn vị. Sau mỗi truy vấn, hãy cho biết giá trị lớn nhất có thể của dãy.
Dữ liệu:
Dòng đầu: hai số nguyên ().
Dòng thứ hai: số nguyên ().
dòng tiếp theo: mỗi dòng gồm ().
Kết quả: Ghi ra dòng, mỗi dòng là đáp số sau mỗi truy vấn.
Ví dụ:
Dữ liệu:
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
Kết quả:
2
2
0
Giải thích:
Sau truy vấn 1: dãy = [2, 3, 3, 4], giá trị tối ưu = 2.
Sau truy vấn 2: dãy = [4, 3, 3, 4], giá trị tối ưu = 2.
Sau truy vấn 3: dãy = [4, 4, 4, 4], giá trị tối ưu = 0.
Giới hạn:
Subtask #1: 30% số điểm với .
Subtask #2: 30% số điểm với .
Subtask #3: 40% số điểm còn lại không có ràng buộc thêm.
