{"problem":{"name":"F. Fafa and Array","description":{"content":"Fafa has an array _A_ of _n_ positive integers, the function _f_(_A_) is defined as . He wants to do _q_ queries of two types: *   1 _l_ _r_ _x_ — find the maximum possible value of _f_(_A_), if _x_ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF935F"},"statements":[{"statement_type":"Markdown","content":"Fafa has an array _A_ of _n_ positive integers, the function _f_(_A_) is defined as . He wants to do _q_ queries of two types:\n\n*   1 _l_ _r_ _x_ — find the maximum possible value of _f_(_A_), if _x_ is to be added to one element in the range \\[_l_,  _r_\\]. You can choose to which element to add _x_.\n*   2 _l_ _r_ _x_ — increase all the elements in the range \\[_l_,  _r_\\] by value _x_.\n\nNote that queries of type 1 don't affect the array elements.\n\n## Input\n\nThe first line contains one integer _n_ (3 ≤ _n_ ≤ 105) — the length of the array.\n\nThe second line contains _n_ positive integers _a_1, _a_2, ..., _a__n_ (0 < _a__i_ ≤ 109) — the array elements.\n\nThe third line contains an integer _q_ (1 ≤ _q_ ≤ 105) — the number of queries.\n\nThen _q_ lines follow, line _i_ describes the _i_\\-th query and contains four integers _t__i_ _l__i_ _r__i_ _x__i_ .\n\nIt is guaranteed that at least one of the queries is of type 1.\n\n## Output\n\nFor each query of type 1, print the answer to the query.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Fafa 有一个包含 #cf_span[n] 个正整数的数组 #cf_span[A]，函数 #cf_span[f(A)] 定义为 。他希望进行 #cf_span[q] 次两种类型的查询：\n\n注意，类型为 #cf_span[1] 的查询不会影响数组元素。\n\n第一行包含一个整数 #cf_span[n] #cf_span[(3 ≤ n ≤ 105)] —— 数组的长度。\n\n第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an] #cf_span[(0 < ai ≤ 109)] —— 数组元素。\n\n第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 查询的数量。\n\n接下来 #cf_span[q] 行，第 #cf_span[i] 行描述第 #cf_span[i] 个查询，包含四个整数 #cf_span[ti li ri xi] 。\n\n保证至少有一个查询是类型 #cf_span[1]。\n\n对于每个类型为 #cf_span[1] 的查询，请输出该查询的答案。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] #cf_span[(3 ≤ n ≤ 105)] —— 数组的长度。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an] #cf_span[(0 < ai ≤ 109)] —— 数组元素。第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 查询的数量。然后 #cf_span[q] 行，第 #cf_span[i] 行描述第 #cf_span[i] 个查询，包含四个整数 #cf_span[ti li ri xi] 。保证至少有一个查询是类型 #cf_span[1]。\n\n## Output\n\n对于每个类型为 #cf_span[1] 的查询，请输出该查询的答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers.  \nLet $ q \\in \\mathbb{Z} $ be the number of queries.  \nEach query is a tuple $ (t_i, l_i, r_i, x_i) \\in \\{1,2\\} \\times \\mathbb{Z}^3 $, with $ 1 \\leq l_i \\leq r_i \\leq n $ and $ x_i \\in \\mathbb{Z}^+ $.\n\n**Constraints**  \n1. $ 3 \\leq n \\leq 10^5 $  \n2. $ 0 < a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq q \\leq 10^5 $  \n4. For each query $ i $:  \n   - $ 1 \\leq l_i \\leq r_i \\leq n $  \n   - $ x_i > 0 $  \n   - At least one query has $ t_i = 1 $\n\n**Objective**  \nFor each query $ i $:  \n- If $ t_i = 1 $: compute and output $ \\sum_{j=l_i}^{r_i} a_j $  \n- If $ t_i = 2 $: update $ a_{l_i} \\gets a_{l_i} + x_i $, $ a_{r_i} \\gets a_{r_i} + x_i $ (note: if $ l_i = r_i $, update only once)  \n\n*(Note: The function $ f(A) $ is not defined in the input, but the query type 1 clearly implies a range sum; type 2 updates two endpoints.)*","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF935F","tags":["data structures","greedy"],"sample_group":[["5\n1 1 1 1 1\n5\n1 2 4 1\n2 2 3 1\n2 4 4 2\n2 3 4 1\n1 3 3 2","2\n8"],["5\n1 2 3 4 5\n4\n1 2 4 2\n2 2 4 1\n2 3 4 1\n1 2 4 2","6\n10"]],"created_at":"2026-03-03 11:00:39"}}