F. Телебашни
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд расположены $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$.

В городах строятся телебашни. У телебашни, расположенной в $$$i$$$-м городе, есть высота $$$h_i$$$ и радиус вещания $$$w_i$$$. Эта башня может вещает в городе $$$j$$$, если и только если выполнены следующие условия:

  • $$$i \le j \le w_i$$$, и
  • для всех $$$k$$$ таких, что $$$i < k \le j$$$, выполняется $$$h_k < h_i$$$.
Другими словами, телебашня в городе $$$i$$$ вещает в городе $$$j$$$, если $$$j \ge i$$$, $$$j$$$ находится в радиусе вещания $$$i$$$-й телебашни, и $$$i$$$-я телебашня строго выше всех башен между городами $$$i$$$ и $$$j$$$ (включая город $$$j$$$).

Изначально во всех городах $$$i$$$ выполняется $$$h_i = 0$$$ и $$$w_i = i$$$.

Затем происходят $$$q$$$ событий. $$$i$$$-е событие может быть одним из следующих:

  • Город $$$c_i$$$ реконструирует свою телебашню так, что она станет самой высокой среди всех телебашен, и при этом ее радиус вещания $$$w_{c_i}$$$ станет равным $$$g_i$$$.
  • Пусть $$$b_j$$$ равно количеству телебашен, вещающих в городе $$$j$$$. Вам нужно вычислить сумму $$$b_j$$$ по всем $$$j$$$, удовлетворяющим $$$l_i \le j \le r_i$$$.

Ваша задача — обрабатывать все события и вывести ответ на все запросы.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2\cdot10^5$$$) — количество городов и количество событий.

Далее следуют $$$q$$$ строк. $$$i$$$-я из этих строк начинается с одного целого числа $$$p_i$$$ ($$$p_i = 1$$$ или $$$p_i = 2$$$).

Если $$$p_i = 1$$$, то реконструируется одна из телебашен. Далее следуют два целых числа $$$c_i$$$ и $$$g_i$$$ ($$$1 \le c_i \le g_i \le n$$$) — город, в котором реконструируется башня, и новый радиус вещания.

Если $$$p_i = 2$$$, то вам нужно ответить на запрос. Далее следуют два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы отрезка городов в запросе.

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

Для каждого запроса выведите сумму $$$b_j$$$ в данном отрезке.

Примеры
Входные данные
1 3
2 1 1
1 1 1
2 1 1
Выходные данные
1
1
Входные данные
5 10
1 3 4
2 3 5
1 1 5
2 1 5
1 4 5
2 2 4
1 2 3
2 1 3
1 5 5
2 2 5
Выходные данные
4
10
5
4
5
Примечание

В первом примере единственная телебашня в городе $$$1$$$ вещает в городе $$$1$$$ до и после реконструкции.

Во втором примере после каждой реконструкции массив $$$b$$$ выглядят следующим образом:

  1. $$$[1, 1, 1, 2, 1]$$$;
  2. $$$[1, 2, 2, 3, 2]$$$;
  3. $$$[1, 2, 2, 1, 2]$$$;
  4. $$$[1, 1, 2, 1, 2]$$$;
  5. $$$[1, 1, 2, 1, 1]$$$.