Thay đổi dữ liệu (DHBB 2023)

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Dữ liệu tài chính của một công ty trong $n$ ngày được biểu diễn bằng một dãy số $t_1,t_2,\dots,t_n$ , trong đó $t_i\ (1\le i\le n)$ là dữ liệu cho ngày thứ $i$ , nếu $t_i\ge 0$ tức là ngày $i$ công ty thu về $t_i$ đồng, ngược lại $t_i<0$ tức là ngày $i$ công ty phải chi $|t_i|$ đồng. Lãnh đạo công ty thường thống kê số liệu về tổng thu chi của một dãy ngày liên tiếp mà có biến động lớn nhất, mức đánh giá biến động từ ngày $L$ đến ngày $R$ được tính bằng $|\sum_{i=L}^R t_i|$ .

Một nhân viên đã truy cập trái phép dữ liệu của công ty trước khi lãnh đạo công ty thống kê số liệu, nhân viên đã thay đổi số liệu của một dãy các ngày liên tiếp từ ngày $u$ đến ngày $v\ (1\le u\le v\le n)$ một lượng $c$ , cụ thể với ngày $i\ (u\le i\le v)$ giá trị $t_i$ được thay đổi bằng $t_i+c$ . Sau khi thống kê số liệu xong, nhân viên này sẽ lại thay đổi dữ liệu như ban đầu.

Yêu cầu: Cho biết dữ liệu ban đầu là $t_1,t_2,\dots,t_n$ và $q$ giả định thay đổi số liệu, với mỗi giả định hãy cho biết giá trị $|\sum_{i=L}^R t_i|$ lớn nhất với $1\le L\le R\le n$ .

Input, Output và Subtasks

Input

Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

Dòng đầu chứa hai số nguyên dương $n,q$ ;
Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots,t_n\ (|t_i|\le 10^9)$ ;
Dòng thứ $k\ (1\le k\le q)$ trong $q$ dòng sau, mỗi dòng chứa ba số nguyên mô tả giả định thay đổi số liệu $u,v,c\ (1\le u\le v\le n, |c|\le 10^9)$ .

Output

Ghi ra thiết bị ra chuẩn (màn hình) gồm $q$ dòng, mỗi dòng chứa một số nguyên là giá trị mà lãnh đạo công ty thống kê được tương ứng với giả định trong file dữ liệu vào.

Scoring

Subtask 1 ( $15$ điểm): $n,q\le 20$
Subtask 2 ( $15$ điểm): $n,q\le 5000$
Subtask 3 ( $20$ điểm): $n,q\le 10^5$ và cả $q$ giả định có $v-u\le 20$
Subtask 4 ( $30$ điểm): $n,q\le 10^5$ và số cặp $(u,v)$ khác nhau trong $q$ giả định không quá $20$ cặp
Subtask 5 ( $20$ điểm): $n,q\le 10^5$

Sample

Input

Output

4
4

Note

Dữ liệu thay đổi theo giả định thứ nhất: $1\ -3\ 2\ 1\ 1$ , kết quả thống kê được là $4$ (đoạn từ $3$ đến $5$ )
Dữ liệu thay đổi theo giả định thứ hai: $1\ -3\ 0\ -1\ 1$ , kết quả thống kê được là $4$ (đoạn từ $2$ đến $4$ )

Bình luận

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