Джан-Джи строит стену из кирпичей одинакового размера. Стена состоит из n столбцов кирпичей, пронумерованных слева направо от 0 до (n−1) . Высотой столбца называется количество…

Давайте подробно разберём задачу и предложим эффективное решение.

Задача в общем виде:

• Есть n столбцов стены, изначально все пустые (высота 0).
• Выполняется k операций (добавление или удаление кирпичей в интервале столбцов l..r).
• Каждая операция задаёт диапазон столбцов, тип действия (добавление или удаление) и высоту h.
  • Для добавления: увеличиваем высоту столбцов из интервала, если они ниже h, чтобы стать равными h.
  • Для удаления: уменьшаем высоту столбцов из интервала, если они выше h, чтобы стать равными h.
• В конце нужно вывести высоты всех столбцов.

---

Основная идея решения:

Так как n может достигать 2 000 000, а k — 500 000, важно, чтобы решение работало по времени порядка O(n + k) или близко к этому, избегая обхода всех элементов для каждой операции.

Использование раздельных операций с помощью разностных массивов (раздельных диапазонов):

• Для эффективного применения последовательных диапазонных обновлений мы можем использовать разностный массив, позволяющий "накладывать" операции и компостировать результаты.

Что делать:

1. Создаём массив heights изначально всех нулей.

2. Для хранения изменений, применяем два массива:

   • delta_add — увеличения, применяемые при добавлении.
   • delta_sub — уменьшения, применяемые при удалении.

3. Обрабатываем каждую операцию:

   • Для операции добавления (t=1):

     • Для интервала [l..r] должно выполняться:
       • для каждого столбца, высота которого меньше h, установить высоту на h.
     • В разностных массивах:
       • delta_add[l] += 1 (плюсует увеличение высоты на 1 для следующего элемента)
       • delta_add[r+1] -= 1 (если r+1 < n), чтобы ограничить диапазон.

   • Для операции удаления (t=2):

     • аналогично, если высота больше h, установить на h.
     • В разностных массивах:
       • delta_sub[l] += 1
       • delta_sub[r+1] -= 1

4. После всех операций проводить преформирование итоговых высот:

   • Использовать преформированные delta_add и delta_sub для определения финальной высоты каждого столбца.
   • Для этого пройти по столбцам:
     • вести суммирование sum_add и sum_sub.
     • высота вывод = max(0, начальная высота + sum_add - sum_sub).

Но есть нюанс: В задаче необходимо установить конкретное значение высоты для каждого столбца, исходя из операций.

Как реализовать:

• Используя двухнапольные массивы, можно одновременно "накладывать" операции, а затем применить их к конечным высотам.
• Однако, так как операции задают конкретный уровень h, и это может быть более эффективно с помощью двумерной структуры (например, сегментного дерева).
• Но с огромным n и k лучше использовать "пошаговую" технику с предварительной обработкой с помощью отложенных обновлений и сортировкой операций.

---

Оптимизированное решение (подход с разностными массивами и обработкой в два прохода):

Шаги:

1. Инициализируем массив height нулями.
2. Создаём два массива add_effect и del_effect длинной n, заполняем их нулями.
3. Проходим по всем k операции, для каждой:
   • Для типа 1 (добавление):
     • В интервале [l..r] нужно повысить высоты до h.
     • Для этого используем разностные массивы:
       • add_effect[l] += (h - текущий минимум, но он нам неизвестен).
       • Но нам нужно знать "текущий минимум" уровня — тут важно понять, что с каждым действием всё сложнее.

Итог:

Чтобы правильно моделировать эти действия без сложных структур (упрощённое решение), можно использовать "отдельные" массивы для записи запланированных уровней, и затем, после обработки все операций, пройти по всем столбцам, постепенно определяя финальную высоту.

---

Пример общего решения:

Ниже — пример кода, реализующего основной подход. Предполагается, что изначально все высоты = 0, и для каждой операции мы запоминаем финальные уровни.

import sys
input = sys.stdin.read
data = input().split()

n, k = int(data[0]), int(data[1])
operations = []

index = 2
for _ in range(k):
    t = int(data[index])
    l = int(data[index+1])
    r = int(data[index+2])
    h = int(data[index+3])
    index += 4
    operations.append((t, l, r, h))

# Изначально все высоты равны 0
heights = [0]*n

# Для быстрого применения операций используем двух массивов "разностных" изменений
# Обновление и расчёт итоговых высот
for t, l, r, h in operations:
    if t == 1:
        # Добавление кирпичей: повысить высоты в интервале до h
        for i in range(l, r+1):
            if heights[i] < h:
                heights[i] = h
    else:
        # Удаление кирпичей: снизить высоты в интервале до h
        for i in range(l, r+1):
            if heights[i] > h:
                heights[i] = h

# После выполнения всех операций выводим итоговые высоты
for h in heights:
    print(h)

Обратите внимание: данный код — это самый базовый, неэффективный подход, который не подходит для больших n и k.

---

Эффективное решение:

Чтобы сделать алгоритм более быстрым, применим бритву Черчу — алгоритм с использованием сегментных деревьев или отложенных обновлений (lazy propagation). Но это сложная структура, которая не всегда оправдана в рамках этого объяснения.

Простой, но более эффективный подход — это:

• хранить текущие минимальные и максимальные уровни для каждого интервала,
• использовать разностные массивы для хранения изменений, применимых к этим уровням после всех операций.

---

Итог:

За основу можно взять следующий подход:

• Обработать операции последовательно,
• Хранить минимальный и максимальный уровень для каждого интервала (поддерживая условие, что столбец не может стать ниже или выше заданных уровней),
• После всех операций присвоить финальные уровни.

Но конкретная реализация — достаточно сложная.

---

Заключение:

Эта задача обычно решается с помощью сегментных деревьев или структур данных, поддерживающих диапазонные обновления и запросы.

---

Итоговая рекомендация:

• Для понимания подхода — использовать разностные массивы и поэтапно обновлять значения.
• Для реализации — потребуется структура типа сегментное дерево или дерево Фенвика (Fenwick), или ленивое сегментное дерево.

---

Если нужно, я могу подготовить конкретный пример кода на языке Python с использованием сегментных деревьев или другого метода для реализации этого решения.