← 返回题目列表

Codeforces · 1406/D

D. 三个序列

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 整数序列 $$$a_1, a_2, \ldots, a_n$$$。

您必须构造两个整数序列 $$$b$$$ 和 $$$c$$$ ,长度为 $$$n$$$ 满足:

- 对于每个 $$$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$$$ ($$$1\leq i\leq 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$$$-th ($$$1 \leq i \leq q+1$$$) 行,打印 $$$i-1$$$ 更改后序列问题的答案。

示例

输入 #1

4
2 -1 7 3
2
2 4 -3
3 4 2

输出 #1

5
5
6

输入 #2

6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

输出 #2

3
3
3
1

输入 #3

1
0
2
1 1 -1
1 1 -1

输出 #3

0
0
-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)$$$ 是一个可能的选择。