CF1887C.Minimum Array

给定一个长度为 $n$ 的整数数组 $a$。然后对其顺序执行 $q$ 次如下操作：

• 选择下标 $l$ 和 $r$（$1 \le l \le r \le n$）以及一个整数 $x$；
• 将 $x$ 加到数组 $a$ 的区间 $[l, r]$ 的所有元素上。更正式地说，对所有 $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$ 如果存在某个下标 $i$ 使得 $x_i < y_i$，且对于所有 $j < i$ 都有 $x_j = y_j$，则数组 $x$ 的字典序小于数组 $y$。换句话说，对于第一个不同的位置 $i$，若 $x_i < y_i$，则 $x$ 的字典序小于 $y$。

每组测试数据包含多个测试用例。第一行包含一个整数 $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$ 中字典序最小的数组。

在第一个测试用例中：

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

因此，字典序最小的数组是 $b_2$。

在第二个测试用例中，字典序最小的数组是 $b_0$。

由 ChatGPT 4.1 翻译