310794: CF1888F. Minimum Array

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Minimum Arraytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given an array $a$ of length $n$ consisting of integers. Then the following operation is sequentially applied to it $q$ times:

  • Choose indices $l$ and $r$ ($1 \le l \le r \le n$) and an integer $x$;
  • Add $x$ to all elements of the array $a$ in the segment $[l, r]$. More formally, assign $a_i := a_i + x$ for all $l \le i \le r$.

Let $b_j$ be the array $a$ obtained after applying the first $j$ operations ($0 \le j \le q$). Note that $b_0$ is the array $a$ before applying any operations.

You need to find the lexicographically minimum$^{\dagger}$ array among all arrays $b_j$.

$^{\dagger}$An array $x$ is lexicographically smaller than array $y$ if there is an index $i$ such that $x_i < y_i$, and $x_j = y_j$ for all $j < i$. In other words, for the first index $i$ where the arrays differ, $x_i < y_i$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the elements of array $a$.

The third line of each test case contains a single integer $q$ ($0 \le q \le 5 \cdot 10^5$) — the number of operations on the array.

In each of the next $q$ lines, there are three integers $l_j$, $r_j$, and $x_j$ $(1 \le l_j \le r_j \le n, -10^9 \le x_j \le 10^9)$ — the description of each operation. The operations are given in the order they are applied.

It is guaranteed that the sum of $n$ over all test cases and the sum of $q$ over all test cases do not exceed $5 \cdot 10^5$.

Output

For each test case, output the lexicographically minimum array among all arrays $b_j$.

ExampleInput
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
Output
-99 -98 -97 4 
2 1 2 5 4 
Note

In the first test case:

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

Thus, the lexicographically minimum array is $b_2$.

In the second test case, the lexicographically minimum array is $b_0$.

Output

题目大意:
给定一个长度为n的整数数组a。然后按照顺序对它执行q次以下操作:
1. 选择索引l和r(1≤l≤r≤n)和一个整数x;
2. 将x加到数组a中在区间[l, r]内的所有元素上。更正式地说,对所有l≤i≤r,赋值a_i := a_i + x。
令b_j为执行前j次操作后得到的数组a(0≤j≤q)。注意b_0是执行任何操作之前的数组a。
你需要找到所有数组b_j中字典序最小的数组。

输入数据格式:
每个测试包含多个测试用例。第一行包含一个整数t(1≤t≤5×10^5)——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n(1≤n≤5×10^5)——数组a的长度。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n(-10^9≤a_i≤10^9)——数组a的元素。
每个测试用例的第三行包含一个整数q(0≤q≤5×10^5)——对数组进行的操作数量。
在接下来的q行中,每行有三个整数l_j, r_j, 和x_j(1≤l_j≤r_j≤n, -10^9≤x_j≤10^9)——每次操作的描述。操作按它们执行的顺序给出。
保证所有测试用例的n之和以及所有测试用例的q之和不超过5×10^5。

输出数据格式:
对于每个测试用例,输出所有数组b_j中字典序最小的数组。题目大意: 给定一个长度为n的整数数组a。然后按照顺序对它执行q次以下操作: 1. 选择索引l和r(1≤l≤r≤n)和一个整数x; 2. 将x加到数组a中在区间[l, r]内的所有元素上。更正式地说,对所有l≤i≤r,赋值a_i := a_i + x。 令b_j为执行前j次操作后得到的数组a(0≤j≤q)。注意b_0是执行任何操作之前的数组a。 你需要找到所有数组b_j中字典序最小的数组。 输入数据格式: 每个测试包含多个测试用例。第一行包含一个整数t(1≤t≤5×10^5)——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n(1≤n≤5×10^5)——数组a的长度。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n(-10^9≤a_i≤10^9)——数组a的元素。 每个测试用例的第三行包含一个整数q(0≤q≤5×10^5)——对数组进行的操作数量。 在接下来的q行中,每行有三个整数l_j, r_j, 和x_j(1≤l_j≤r_j≤n, -10^9≤x_j≤10^9)——每次操作的描述。操作按它们执行的顺序给出。 保证所有测试用例的n之和以及所有测试用例的q之和不超过5×10^5。 输出数据格式: 对于每个测试用例,输出所有数组b_j中字典序最小的数组。

加入题单

上一题 下一题 算法标签: