В лаборантской 325 есть $$$n$$$ шкафов. На них возложена большая задача — хранить памятные фото и конфеты олимпиадников. Но есть проблема: у любого хранилища есть предел, а у шкафов ножки, поэтому как только в шкафу набирается определённое число предметов $$$lim_i$$$, ножки ломаются а шкаф падает. Всё бы ничего если бы за раз мог упасть только один шкаф, но ведь они стоят друг рядом с другом и каждый имеет свою высоту $$$h_i$$$, поэтому если падает шкаф на позиции $$$i$$$, то упадут все шкафы на отрезке $$$[i;i+h_i-1]$$$, они в свою очередь повалят какие-то свои отрезки.
Вы могли бы спасти ситуацию в лаборантской, но для этого нужна поддержка фонда Спидвагона. Поэтому остаётся лишь следить за ситуацией. По сути вам необходимо обрабатывать $$$q$$$ запросов, которые бывают двух типов:
В первой строке заданы два целых положительных числа $$$n$$$ и $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$). Далее следует $$$n$$$ строк описания шкафов, каждая содержит два целых числа $$$h_i$$$ и $$$lim_i$$$ ($$$1 \leq h_i \ , \ lim_i \leq 10^9$$$).
Последние $$$q$$$ строк содержат описание запросов. Границы запросов лежат в отрезке от $$$1$$$ до $$$n$$$, а также гарантируется, что $$$l_i \leq r_i$$$ для всех запросов. Количество предметов, которые могут быть добавлены за один запрос, не превышает $$$10^9$$$.
Для каждого запроса второго типа выведите в отдельной строке количество целых шкафов на момент запроса.
| Группа | Дополнительные ограничения | Баллы | Зависит от |
| $$$1$$$ | $$$n,q \le 2000$$$ | $$$18$$$ | – |
| $$$2$$$ | сначала все запросы типа 1, а потом типа 2 | $$$31$$$ | – |
| $$$3$$$ | для всех запросов $$$l=r$$$ | $$$17$$$ | – |
| $$$4$$$ | $$$l = r$$$ для всех запросов типа 1 | $$$9$$$ | 3 |
| $$$5$$$ | нет дополнительных ограничений | $$$25$$$ | 1, 2, 3, 4 |
5 41 12 22 31 41 51 2 4 11 1 2 22 1 12 1 5
0 1
| Vitebsk Open 2024 day 1 |
|---|
| Finished |
