Задача №115168. Минимальный массив
Дан массив \(a\) длины \(n\), состоящий из целых чисел. Далее к нему последовательно \(q\) раз применяют следующую операцию:
-
Выбирают индексы \(l\) и \(r\) (\(1 \le l \le r \le n\)) и целое число \(x\);
-
Ко всем элементам массива \(a\) на отрезке \([l, r]\) прибавляют \(x\). Более формально, присваивают \(a_i := a_i + x\) для всех \(l \le i \le r\).
Пусть \(b_j\) — массив \(a\), полученный после применения первых \(j\) операций (\(0 \le j \le q\)). Обратите внимание, что \(b_0\) — это массив \(a\) до применения всех операций.
Вам нужно найти лексикографически минимальный\(^{\dagger}\) массив среди всех \(b_j\).
\(^{\dagger}\)Массив \(x\) лексикографически меньше чем массив \(y\), если есть индекс \(i\) такой, что \(x_i < y_i\), и \(x_j = y_j\) для всех \(j < i\). Иными словами, для первого такого индекса \(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\).
В первом наборе входных данных:
-
\(b_0 = [1,2,3,4]\);
-
\(b_1 = [1,2,3,4]\);
-
\(b_2 = [-99,-98,-97,4]\).
Таким образом, лексикографически минимальным является массив \(b_2\).
Во втором наборе входных данных лексикографически минимальным является массив \(b_0\).
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
-99 -98 -97 4 2 1 2 5 4