COCI 2020/2021 - Contest 5 - Sjeckanje
View as PDFPaula rất thích nấu ăn, và để chuẩn bị một món ăn ngon thì Paula phải cắt một dãy số gồm ~n~ số nguyên ra các đoạn với tổng giá trị lớn nhất.
Giá trị của một đoạn được định nghĩa là hiệu giữa phần tử lớn nhất và bé nhất trong đoạn. Giá trị của một dãy đã được cắt là tổng giá trị của các đoạn.
Ví dụ, chúng ta cắt dãy ~[1,4,1,5,3,6]~ thành 2 dãy con ~[1, 4, 1]~ và ~[5, 3, 6]~ thì giá trị của dãy sẽ là ~(4-1)+(6-3)=6~
Sẽ có ~q~ truy vấn có dạng "thêm ~x~ vào các phần tử có số thứ tự ~l,l+1,...,r~". Sau mỗi truy vấn, trả lời câu hỏi "Giá trị lớn nhất có thể của dãy là bao nhiêu?"
Input
Dòng đầu tiên gồm số nguyên ~n~ và ~q~ ~(1 \le n,q \le 200000)~, độ dài của dãy và số truy vấn.
Dòng thứ hai gồm n số nguyên ~a_i~ ~(-10^8 \le a_i \le 10^8)~, dãy số Paula cần cắt.
Mỗi trong ~q~ dòng tiếp theo gồm 2 số nguyên ~l,r~ ~(1 \le l \le r \le n)~ và ~x~ ~(-10^8 \le x \le 10^8)~, mô tả một truy vấn.
Output
In ra ~q~ dòng, là đáp án sau mỗi truy vấn.
Sample 1
Input
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
Output
2
2
0
Sample 2
Input
4 3
2 0 2 1
4 4 1
2 2 3
1 3 2
Output
2
1
3
Giải thích Sample 1
Cách cắt tối ưu sau các lần update lần lượt là ~[2,3,3,4] , [4,3] [3,4] , [4, 4, 4, 4]~
Subtask
- ~8~ test đầu có ~1 \le n,q \le 200~
- ~6~ test tiếp theo có ~1 \le n,q \le 3000~
- ~6~ test còn lại không có điều kiện gì thêm
Comments
This comment is hidden due to too much negative feedback. Show it anyway.