← 返回题目列表

Codeforces · 1887/C

C. 最小数组

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

给定一个由整数组成的长度为 $$$n$$$ 的数组 $$$a$$$。然后按顺序对其应用以下操作 $$$q$$$ 次:

- 选择索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 和一个整数 $$$x$$$;
- 将 $$$x$$$ 添加到 $$$[l, r]$$$ 段中数组 $$$a$$$ 的所有元素。更正式地说,为所有 $$$l \le i \le r$$$ 分配 $$$a_i := a_i + x$$$。

令 $$$b_j$$$ 为应用第一个 $$$j$$$ 操作后获得的数组 $$$a$$$ ($$$0 \le j \le q$$$)。请注意,$$$b_0$$$ 是应用任何操作之前的数组 $$$a$$$。

你需要在所有数组$$$b_j$$$中找到字典顺序最小的$$$^{\dagger}$$$数组。

$$$^{\dagger}$$$如果存在索引$$$i$$$,使得$$$x_i < y_i$$$,并且对于所有$$$j < i$$$,$$$x_j = y_j$$$,则数组$$$x$$$按字典顺序小于数组$$$y$$$。换句话说,对于数组不同的第一个索引 $$$i$$$,$$$x_i < y_i$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含一个整数 $$$q$$$ ($$$0 \le q \le 5 \cdot 10^5$$$) — 数组上的操作数。

在接下来的 $$$q$$$ 行中,有三个整数 $$$l_j$$$、$$$r_j$$$ 和 $$$x_j$$$ $$$(1 \le l_j \le r_j \le n, -10^9 \le x_j \le 10^9)$$$ — 每个操作的描述。这些操作按照它们的应用顺序给出。

保证所有测试用例的 $$$n$$$ 之和以及所有测试用例的 $$$q$$$ 之和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,输出所有数组 $$$b_j$$$ 中按字典顺序排列的最小数组。

示例

输入 #1

2
4
1 2 3 4
2
1 4 0
1 3 -100
5
2 1 2 5 4
3
2 4 3
2 5 -2
1 3 1

输出 #1

-99 -98 -97 4 
2 1 2 5 4

注意

在第一个测试用例中:

- $$$b_0 = [1,2,3,4]$$$;
- $$$b_1 = [1,2,3,4]$$$;
- $$$b_2 = [-99,-98,-97,4]$$$。

因此,按字典顺序排列的最小数组是 $$$b_2$$$。

在第二个测试用例中,按字典顺序排列的最小数组是 $$$b_0$$$。