{"code":"querysums","name":"QUERYSUMS","description":"Cho dãy $a$ gồm $n$ phần tử được đánh chỉ số từ $1$ đến $n$ và $q$ truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:\r\n\r\n 1. Tăng các phần tử từ chỉ số $l$ đến $r$ thêm $x$.\r\n 2. Tìm giá trị lớn nhất của biểu thức $a_{i_1} - a_{i_2} + a_{i_3} - a_{i_4} + \\ldots$ với $i_1, i_2, i_3, i_4, \\ldots$ là các chỉ số được chọn thỏa mãn $l \\leq i_1 < i_2 < i_3 < i_4 < \\ldots \\leq r$. Nếu không chọn chỉ số nào thì giá trị của biểu thức là $0$.\r\n\r\n<h4>Input</h4>\r\n\r\n - Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \\leq n, q \\leq 10 ^ 5$).\r\n - Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \\ldots, a_n$ ($|a_i| \\leq 10 ^ 9$).\r\n - Trong $q$ dòng tiếp theo, mỗi dòng chứa số nguyên $1$ hoặc $2$. Số $1$ theo sau bởi ba số nguyên $l$, $r$ và $x$ ($1 \\leq l \\leq r \\leq n$, $|x| \\leq 10 ^ 9$) mô tả truy vấn loại 1. Số $2$ theo sau bởi hai số nguyên $l$ và $r$ ($1 \\leq l \\leq r \\leq n$) mô tả truy vấn loại 2.\r\n\r\n<h4>Output</h4>\r\n\r\n - Với mỗi truy vấn loại 2, in ra giá trị lớn nhất của biểu thức trên một dòng. \r\n\r\n<h4>Scoring</h4>\r\n\r\n- Subtask 1 (30% số điểm): $n, q \\leq 20$.\r\n- Subtask 2 (30% số điểm): $n, q \\leq 10 ^ 3$.\r\n- Subtask 3 (30% số điểm): Truy vấn loại 1 có $l = r$.\r\n- Subtask 4 (10% số điểm): Không có ràng buộc gì thêm.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 5\r\n        9 3 -2 5 -1\r\n        2 1 3\r\n        1 4 5 6\r\n        2 2 5\r\n        1 2 2 -7\r\n        2 2 3\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        11\r\n        16\r\n        0\r\n        ```\r\n    ??? warning \"Note\"\r\n        - Ban đầu, dãy $a$ là $[9, 3, -2, 5, -1]$.\r\n        - Ở truy vấn thứ nhất, cách tối ưu là chọn các chỉ số $i_1 = 1$ và $i_2 = 3$. Khi đó, giá trị của biểu thức là $a_1 - a_3 = 11$.\r\n        - Ở truy vấn thứ hai, sau khi tăng các phần tử từ chỉ số $4$ đến $5$ thêm $6$, ta được dãy $a$ mới là $[9, 3, -2, 11, 5]$.\r\n        - Ở truy vấn thứ ba, cách tối ưu là chọn các chỉ số $i_1 = 2$, $i_2 = 3$ và $i_3 = 4$. Khi đó, giá trị của biểu thức là $a_2 - a_3 + a_4 = 16$.\r\n        - Ở truy vấn thứ tư, sau khi tăng các phần tử từ chỉ số $2$ đến $2$ thêm $-7$, ta được dãy $a$ mới là $[9, -4, -2, 11, 5]$.\r\n        - Ở truy vấn thứ năm, cách tối ưu là không chọn chỉ số nào. Khi đó, giá trị của biểu thức là $0$.","points":2000.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}