{"problem":{"name":"E. Mahmoud and Ehab and the function","description":{"content":"Dr. Evil is interested in math and functions, so he gave Mahmoud and Ehab array _a_ of length _n_ and array _b_ of length _m_. He introduced a function _f_(_j_) which is defined for integers _j_, whic","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF862E"},"statements":[{"statement_type":"Markdown","content":"Dr. Evil is interested in math and functions, so he gave Mahmoud and Ehab array _a_ of length _n_ and array _b_ of length _m_. He introduced a function _f_(_j_) which is defined for integers _j_, which satisfy 0 ≤ _j_ ≤ _m_ - _n_. Suppose, _c__i_ = _a__i_ - _b__i_ + _j_. Then _f_(_j_) = |_c_1 - _c_2 + _c_3 - _c_4... _c__n_|. More formally, .\n\nDr. Evil wants Mahmoud and Ehab to calculate the minimum value of this function over all valid _j_. They found it a bit easy, so Dr. Evil made their task harder. He will give them _q_ update queries. During each update they should add an integer _x__i_ to all elements in _a_ in range \\[_l__i_;_r__i_\\] i.e. they should add _x__i_ to _a__l__i_, _a__l__i_ + 1, ... , _a__r__i_ and then they should calculate the minimum value of _f_(_j_) for all valid _j_.\n\nPlease help Mahmoud and Ehab.\n\n## Input\n\nThe first line contains three integers _n_, _m_ and _q_ (1 ≤ _n_ ≤ _m_ ≤ 105, 1 ≤ _q_ ≤ 105) — number of elements in _a_, number of elements in _b_ and number of queries, respectively.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_. ( - 109 ≤ _a__i_ ≤ 109) — elements of _a_.\n\nThe third line contains _m_ integers _b_1, _b_2, ..., _b__m_. ( - 109 ≤ _b__i_ ≤ 109) — elements of _b_.\n\nThen _q_ lines follow describing the queries. Each of them contains three integers _l__i_ _r__i_ _x__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_,  - 109 ≤ _x_ ≤ 109) — range to be updated and added value.\n\n## Output\n\nThe first line should contain the minimum value of the function _f_ before any update.\n\nThen output _q_ lines, the _i_\\-th of them should contain the minimum value of the function _f_ after performing the _i_\\-th update .\n\n[samples]\n\n## Note\n\nFor the first example before any updates it's optimal to choose _j_ = 0, _f_(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0.\n\nAfter the first update _a_ becomes {11, 2, 3, 4, 5} and it's optimal to choose _j_ = 1, _f_(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6) = |9| = 9.\n\nAfter the second update _a_ becomes {2, 2, 3, 4, 5} and it's optimal to choose _j_ = 1, _f_(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0.\n\nAfter the third update _a_ becomes {1, 1, 2, 3, 4} and it's optimal to choose _j_ = 0, _f_(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Dr. Evil 对数学和函数感兴趣，因此他给了 Mahmoud 和 Ehab 一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。他定义了一个函数 $f(j)$，该函数针对满足 $0 ≤ j ≤ m - n$ 的整数 $j$。设 $c_i = a_i - b_{i + j}$，则 $f(j) = |c_1 - c_2 + c_3 - c_4 + \\dots + (-1)^{n+1} c_n|$。更形式化地，\n\nDr. Evil 希望 Mahmoud 和 Ehab 计算该函数在所有合法 $j$ 上的最小值。他们觉得这太简单了，于是 Dr. Evil 加大了难度：他会给出 $q$ 个更新查询。在每次更新中，他们需要将一个整数 $x_i$ 加到数组 $a$ 的区间 $[l_i; r_i]$ 中的所有元素上，即对 $a_{l_i}, a_{l_i + 1}, \\dots, a_{r_i}$ 都加上 $x_i$，然后计算所有合法 $j$ 对应的 $f(j)$ 的最小值。\n\n请帮助 Mahmoud 和 Ehab。\n\n第一行包含三个整数 $n$, $m$ 和 $q$ ($1 ≤ n ≤ m ≤ 10^5$, $1 ≤ q ≤ 10^5$) —— 分别表示数组 $a$ 的元素个数、数组 $b$ 的元素个数和查询次数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($-10^9 ≤ a_i ≤ 10^9$) —— 数组 $a$ 的元素。\n\n第三行包含 $m$ 个整数 $b_1, b_2, \\dots, b_m$ ($-10^9 ≤ b_i ≤ 10^9$) —— 数组 $b$ 的元素。\n\n接下来 $q$ 行，每行描述一个查询，包含三个整数 $l_i$, $r_i$, $x_i$ ($1 ≤ l_i ≤ r_i ≤ n$, $-10^9 ≤ x_i ≤ 10^9$) —— 表示更新的区间和要加的值。\n\n第一行应输出在任何更新之前函数 $f$ 的最小值。\n\n然后输出 $q$ 行，第 $i$ 行应输出执行第 $i$ 次更新后函数 $f$ 的最小值。\n\n对于第一个例子，在任何更新前，最优选择是 $j = 0$，$f(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0$。\n\n第一次更新后，$a$ 变为 $\\{11, 2, 3, 4, 5\\}$，最优选择是 $j = 1$，$f(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |9| = 9$。\n\n第二次更新后，$a$ 变为 $\\{2, 2, 3, 4, 5\\}$，最优选择是 $j = 1$，$f(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0$。\n\n第三次更新后，$a$ 变为 $\\{1, 1, 2, 3, 4\\}$，最优选择是 $j = 0$，$f(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0$。\n\n## Input\n\n第一行包含三个整数 $n$, $m$ 和 $q$ ($1 ≤ n ≤ m ≤ 10^5$, $1 ≤ q ≤ 10^5$) —— 分别表示数组 $a$ 的元素个数、数组 $b$ 的元素个数和查询次数。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ ($-10^9 ≤ a_i ≤ 10^9$) —— 数组 $a$ 的元素。第三行包含 $m$ 个整数 $b_1, b_2, \\dots, b_m$ ($-10^9 ≤ b_i ≤ 10^9$) —— 数组 $b$ 的元素。接下来 $q$ 行，每行描述一个查询，包含三个整数 $l_i$, $r_i$, $x_i$ ($1 ≤ l_i ≤ r_i ≤ n$, $-10^9 ≤ x_i ≤ 10^9$) —— 表示更新的区间和要加的值。\n\n## Output\n\n第一行应输出在任何更新之前函数 $f$ 的最小值。然后输出 $q$ 行，第 $i$ 行应输出执行第 $i$ 次更新后函数 $f$ 的最小值。\n\n[samples]\n\n## Note\n\n对于第一个例子，在任何更新前，最优选择是 $j = 0$，$f(0) = |(1 - 1) - (2 - 2) + (3 - 3) - (4 - 4) + (5 - 5)| = |0| = 0$。第一次更新后，$a$ 变为 $\\{11, 2, 3, 4, 5\\}$，最优选择是 $j = 1$，$f(1) = |(11 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |9| = 9$。第二次更新后，$a$ 变为 $\\{2, 2, 3, 4, 5\\}$，最优选择是 $j = 1$，$f(1) = |(2 - 2) - (2 - 3) + (3 - 4) - (4 - 5) + (5 - 6)| = |0| = 0$。第三次更新后，$a$ 变为 $\\{1, 1, 2, 3, 4\\}$，最优选择是 $j = 0$，$f(0) = |(1 - 1) - (1 - 2) + (2 - 3) - (3 - 4) + (4 - 5)| = |0| = 0$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq m \\leq 10^5 $, $ 1 \\leq q \\leq 10^5 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $, $ B = (b_1, b_2, \\dots, b_m) \\in \\mathbb{Z}^m $.  \nFor $ j \\in \\{0, 1, \\dots, m - n\\} $, define the sequence $ C_j = (c_{j,1}, c_{j,2}, \\dots, c_{j,n}) $ where $ c_{j,i} = a_i - b_{i+j} $.  \nDefine the function:  \n$$\nf(j) = \\left| \\sum_{i=1}^{n} (-1)^{i-1} c_{j,i} \\right| = \\left| \\sum_{i=1}^{n} (-1)^{i-1} (a_i - b_{i+j}) \\right|\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq m \\leq 10^5 $  \n2. $ 1 \\leq q \\leq 10^5 $  \n3. $ -10^9 \\leq a_i, b_i \\leq 10^9 $  \n4. Each update: $ 1 \\leq l_i \\leq r_i \\leq n $, $ -10^9 \\leq x_i \\leq 10^9 $; add $ x_i $ to $ a_{l_i}, a_{l_i+1}, \\dots, a_{r_i} $\n\n**Objective**  \nCompute $ \\min_{j \\in \\{0, 1, \\dots, m - n\\}} f(j) $ before any updates, and after each of the $ q $ updates.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF862E","tags":["binary search","data structures","sortings"],"sample_group":[["5 6 3\n1 2 3 4 5\n1 2 3 4 5 6\n1 1 10\n1 1 -9\n1 5 -1","0\n9\n0\n0"]],"created_at":"2026-03-03 11:00:39"}}