CF1406D Three Sequences

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。 你需要构造两个长度为 $n$ 的整数序列 $b$ 和 $c$，使得： - 对于每个 $i$（$1 \leq i \leq n$），都有 $b_i + c_i = a_i$； - 序列 $b$ 是非递减的，即对于每个 $1 < i \leq n$，都有 $b_i \geq b_{i-1}$； - 序列 $c$ 是非递增的，即对于每个 $1 < i \leq n$，都有 $c_i \leq c_{i-1}$。 你需要最小化 $\max(b_i, c_i)$，也就是说，最小化 $b$ 和 $c$ 两个序列中的最大值。 此外，会有 $q$ 次修改，第 $i$ 次修改由三个整数 $l, r, x$ 描述。你需要将 $x$ 加到 $a_l, a_{l+1}, \ldots, a_r$ 上。 你需要分别输出初始序列以及每次修改后的序列的最小可能的 $\max(b_i, c_i)$。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）。 第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）。 接下来的 $q$ 行，每行包含三个整数 $l, r, x$（$1 \leq l \leq r \leq n, -10^9 \leq x \leq 10^9$），表示一次修改。

输出 $q+1$ 行。 第 $i$ 行（$1 \leq i \leq q+1$）输出第 $i-1$ 次修改后序列的答案。

在第一个测试样例中： - 初始序列 $a = (2, -1, 7, 3)$。一种可行的 $b=(-3,-3,5,5), c=(5,2,2,-2)$。 - 第一次修改后 $a = (2, -4, 4, 0)$。一种可行的 $b=(-3,-3,5,5), c=(5,-1,-1,-5)$。 - 第二次修改后 $a = (2, -4, 6, 2)$。一种可行的 $b=(-4,-4,6,6), c=(6,0,0,-4)$。 由 ChatGPT 4.1 翻译