3-й этап Республиканской олимпиады по информатике 2021-2022, 1 тур

Есеп B. Тетрис

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

BThero тетрис ойнап отыр. Тетрис алаңың ұзындығы $W$ және биіктігі шексіз болатын тіктөртбұрыш ретінде қарастыруға болады. Ыңғайлы болу үшін алаңды жазықтықта орналастырайық. Алаңның төмендегі сол жақтағы ұяшығы $(1, 1)$ координатында, ал төмендегі оң жақтағы ұяшығы $(W, 1)$ координатасында орналасқан. Ойында кезекпен $q$ екі түрлі оқиға болды:

1. Алаңға $x$-координат бойынша $[l,r]$ кесіндісінде биіктігі $h$ болатын жаңа тіктөртбұрыш құлайды. Ол шексіз биіктіктен бастап басқа тіктөртбұрышқа тірелгенше немесе алаңның түбіне жеткенде дейін құлайды. Бұл тетрис ойынында тіктөртбұрыштарды қозғалтуға болмайды.
2. $y$ деген бүтін санмен бірге сұратым келеді. Осы $y$ биіктігінде қанша ұяшық тіктөртбұрыштардың ішінде екенін жауап беру керек.

BThero ағамызға бүкіл сұратымдарға жауап беруге көмектесіңіз!

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

Кіріс деректердің бірінші жолында $W$ және $q$ бүтін сандары берілген ($1 <= W <= 10^6$, $2 <= q <= 10^5$). Келесі $q$ жолдарда оқиғалардың сипаттамалары берілген. Алдымен бір бүтін сан $t$ — оқиғаның түрі беріледі. Егер $t = 1$ болса, бұл бірінші түрдегі оқиға және сізге қосымша үш бүтін сан $l$, $r$ және $h$ беріледі ($1 <= l <= r <= W$, $1 <= h <= 10^6$). Егер $t = 2$ болса, бұл екінші түрдегі оқиға және сізге қосымша бір бүтін сан $y$ беріледі ($1 <= y <= 10^9$). Оқиғалар арасында кем дегенде бір бірінші түрдегі оқиға және кем дегенде бір екінші түрдегі оқиға бар.

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

Шығыс деректерде бүкіл сұратымдардың жауаптары болу керек.

Система оценки

Есеп $6$ бөлімнен тұрады:

1. $q <= 5000$. $20$ ұпайға бағаланады.
2. Ең бірінші оқиға бірінші түрдегі оқиға, ал бүкіл қалған оқиғалар екінші түрдегі оқиғалар. $10$ ұпайға бағаланады.
3. Бүкіл тіктөртбұрыштардың ұзындығы $1$, ені $1$ және бүкіл сұратымдарда $y <= 10^6$. $10$ ұпайға бағаланады.
4. Бүкіл тіктөртбұрыштардың ұзындығы $1$ және бүкіл сұратымдарда $y <= 10^6$. $20$ ұпайға бағаланады.
5. Бүкіл сұратымдарда $y <= 10^6$. $20$ ұпайға бағаланады.
6. Есептің толық шарттары. $20$ ұпайға бағаланады.

Пример:

Вход

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

Замечание

( Temirlan Satylkhanov )