Областная олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Задача E. Тетрис

$BThero$ играет в тетрис. Поле можно представить как прямоугольник с шириной $W$ и бесконечной высотой. Для удобства скажем что прямоугольник находится на двумерной системе координат. Левая нижняя клетка поля имеет координаты ($1$, $1$), а правая нижняя — ($W$, $1$).

В игре последовательно произошли $q$ событий двух типов:

1. На поле падает новый прямоугольник покрывающий x-отрезок [l,r] и высотой $h$. Он начинает падать с бесконечной высоты и падает до тех пор, пока не уткнется в другой прямоугольник или на дно поля. Заметьте, что в данной вариации тетриса двигать прямоугольники вы не можете.
2. Поступает запрос с одним целым числом $y$. Надо ответить, сколько клеток на высоте $y$ уже заняты прямоугольниками.

Помогите $BThero$ эффективно обработать все события!

Формат входного файла

В первой строке даны два целых числа $W$ и $q$ ($1$ $\le$ $W$ $\le$ $10^6$, $2$ $\le$ $q$ $\le$ $10^5$).

В последующих $q$ строках идут описания событий. Сперва дается одно целое число $t$ — тип события. Если $t$ = $1$, это событие первого типа и вам дополнительно даются три целых числа $l$, $r$ и $h$ ($1$ $\le$ $l$ $\le$ $r$ $\le$ $W$, $1$ $\le$ $h$ $\le$ $10^6$). Если $t$ = $2$, это событие второго типа и вам дополнительно дается одно целое число $y$ ($1$ $\le$ $y$ $\le$ $10^9$).

Гарантируется, что есть хотя бы одно событие первого типа и хотя бы одно событие второго типа.

Формат выходного файла

Выходной файл должен содержать ответы на все события второго типа.

Примеры

Входные данные

13 10
1 7 11 4
2 3
1 4 9 2
2 3
2 5
1 1 3 5
2 5
1 2 4 1
2 6
2 7

Выходные данные

5
5
6
9
6
3