Задача №114767. Большие вызовы
На проектной смене в образовательном центре «Сириус» участники одной из команд проектируют промышленных роботов.
Роботы будут наполнять деталями \(n\) контейнеров, которые стоят в ряд и пронумерованы от \(1\) до \(n\). В \(i\)-й контейнер можно суммарно поместить не больше \(a_i\) деталей. Участники собрали \(m\) роботов. Изначально у \(j\)-го робота имеется \(c_j\) деталей, часть из которых он положит в контейнеры. Также, у \(j\)-го робота есть диапазон действия, задающийся двумя числами \(l_j \le r_j\), означающий, что робот может класть детали только в контейнеры с номерами от \(l_j\) до \(r_j\) включительно. Роботы пытаются суммарно положить в контейнеры как можно больше деталей.
Созданные роботы бывают двух типов. Если тип робота \(t_j = 0\), то его диапазон действия всегда остается неизменным. А роботов типа \(t_j = 1\) можно перепрограммировать. Если контейнер с номером \(x\) выделить как наиболее важный, диапазон действия каждого робота типа \(1\) расширяется минимальным образом, чтобы он стал содержать контейнер \(x\). Более формально, диапазон действия робота номер \(j\), имеющего тип \(1\), изменяется на \([\min(l_j, x), \max(r_j, x)]\).
Для каждого \(x\) от \(1\) до \(n\) вычислите, какое максимальное количество деталей роботы смогут суммарно поместить в контейнеры, если важным будет контейнер с номером \(x\), а роботы будут действовать оптимальным образом.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число \(t\) (\(1 \leq t \leq 200\,000\)) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 200\,000\)) — количество контейнеров и роботов соответственно.
В следующей строке даны \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — вместимости контейнеров.
В каждой из следующих \(m\) строк даны по четыре целых числа \(l_j\), \(r_j\), \(c_j\), \(t_j\) (\(1 \le l_j \le r_j \le n\), \(0 \le c_j \le 10^9\), \(t_j \in \{0, 1\}\)) — диапазон действия, изначальное количество деталей и тип робота соответственно.
Обозначим за \(\sum n\) сумму \(n\), а за \(\sum m\) сумму \(m\) по всем наборам входных данных в одном тесте. Гарантируется, что \(\sum n \leq 200\,000\), \(\sum m \leq 200\,000\).
Для каждого набора входных данных выведите \(n\) целых чисел — ответ на задачу для всех \(x\) от \(1\) до \(n\).
| Подз. | Баллы | \(\sum n\) | \(\sum m\) | дополнительно | Необх. подзадачи | Информация о проверке |
| 1 | 10 | \(\sum n \leq 100\) | \(\sum m \leq 100\) | \(m = 1\) | первая ошибка | |
| 2 | 7 | \(\sum n \leq 100\) | \(\sum m \leq 100\) | У, 1 | первая ошибка | |
| 3 | 6 | \(\sum n \leq 2000\) | \(\sum m \leq 2000\) | У, 1–2 | первая ошибка | |
| 4 | 6 | \(\sum n \leq 20\,000\) | \(\sum m \leq 200\) | У, 1–2 | первая ошибка | |
| 5 | 12 | \(\sum n \leq 10^5\) | \(\sum m \leq 2000\) | У, 1–4 | первая ошибка | |
| 6 | 17 | \(\sum n \leq 20\,000\) | \(\sum m \leq 20\,000\) | \(t_i = 1\) | первая ошибка | |
| 7 | 8 | \(\sum n \leq 10^5\) | \(\sum m \leq 10^5\) | \(l_i \le l_{i + 1}\), \(r_i \le r_{i + 1}\), \(t_i = 1\) | первая ошибка | |
| 8 | 8 | \(\sum n \leq 10^5\) | \(\sum m \leq 10^5\) | \(t_i = 1\) | 6, 7 | первая ошибка |
| 9 | 13 | \(\sum n \leq 10^5\) | \(\sum m \leq 10^5\) | если \(t_i = 0\), то \(r_i \le 50, n - 50 \le l_i\) | 6–8 | первая ошибка |
| 10 | 4 | \(\sum n \leq 10^5\) | \(\sum m \leq 10^5\) | \(a_i = 1\) | первая ошибка | |
| 11 | 6 | \(\sum n \leq 10^5\) | \(\sum m \leq 10^5\) | У, 1–10 | первая ошибка | |
| 12 | 3 | \(\sum n \leq 2 \cdot 10^5\) | \(\sum m \leq 2 \cdot 10^5\) | У, 1–11 | первая ошибка |
1 4 3 3 3 2 2 1 2 2 0 3 3 3 0 2 2 4 1
8 7 7 8