| Codeforces Round 162 (Div. 1) |
|---|
| Закончено |
Белка Лисска любит орехи. Лисска просит вас посадить ореховые деревья.
Есть n мест (пронумерованных от 1 до n с запада на восток), где можно посадить дерево вдоль улицы. Деревья вырастают на один метр за месяц. В начале каждого месяца вы должны обрабатывать один запрос. Запрос может быть одного из следующих двух типов:
- Посадить дерево высотой h в месте с номером p.
- Срубить x-ое существующее (не срубленное) дерево с запада (где x в 1-индексации). Когда мы срубаем дерево, оно падает вниз и занимает все доступное пространство на месте, где оно стояло. Таким образом, ни одно дерево в этом месте больше посадить нельзя.
После обработки каждого запроса, вы должны вывести длину самой длинной возрастающей подпоследовательности. Подмножество существующих деревьев называется возрастающей подпоследовательностью, если высоты деревьев в нем строго возрастают с запада на восток (например, самое западное дерево в наборе должно иметь самую маленькую высоту). Длина возрастающей подпоследовательности — это количество деревьев в ней.
Обратите внимание, что Лисске не нравятся деревья одинаковой высоты, поэтому гарантируется, что в любой момент времени нет двух деревьев одинаковой высоты.
В первой строке записаны два целых числа: n и m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — количество мест для деревьев и количество запросов.
В следующих m строках записана информация о запросах в следующем формате:
- Если тип i-ого запроса — 1, то i-ая строка содержит три целых числа: 1, pi, и hi (1 ≤ pi ≤ n, 1 ≤ hi ≤ 10), где pi — место нового дерева, а hi — изначальная высота нового дерева.
- Если тип i-ого запроса — 2, то i-ая строка содержит два целых числа: 2 и xi (1 ≤ xi ≤ 10), где xi — это номер дерева, которое мы хотим срубить.
Гарантируется, что входные данные корректны, то есть:
- Для запросов 1 типа pi будут попарно различны.
- Для запросов 2 типа xi не будут превышать текущего количества деревьев.
- В любой момент времени никакие два дерева не имеют одинаковые высоты.
В каждой строке целые числа разделены одиночными пробелами.
Выведите m целых чисел — длину самой длинной возрастающей подпоследовательности после каждого запроса. Разделяйте числа пробельными символами.
4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3
1
2
3
2
2
2
Вы можете видеть состояние улицы после каждого запроса на следующей анимации:
Если Ваш браузер не поддерживает анимацию png, посмотрите версию в gif здесь: http://212.193.37.254/codeforces/images/162/roadtree.gif
