Codeforces Round 162 (Div. 1) |
---|
Закончено |
Белка Лисска любит орехи. Лисска просит вас посадить ореховые деревья.
Есть n мест (пронумерованных от 1 до n с запада на восток), где можно посадить дерево вдоль улицы. Деревья вырастают на один метр за месяц. В начале каждого месяца вы должны обрабатывать один запрос. Запрос может быть одного из следующих двух типов:
После обработки каждого запроса, вы должны вывести длину самой длинной возрастающей подпоследовательности. Подмножество существующих деревьев называется возрастающей подпоследовательностью, если высоты деревьев в нем строго возрастают с запада на восток (например, самое западное дерево в наборе должно иметь самую маленькую высоту). Длина возрастающей подпоследовательности — это количество деревьев в ней.
Обратите внимание, что Лисске не нравятся деревья одинаковой высоты, поэтому гарантируется, что в любой момент времени нет двух деревьев одинаковой высоты.
В первой строке записаны два целых числа: n и m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2·105) — количество мест для деревьев и количество запросов.
В следующих m строках записана информация о запросах в следующем формате:
Гарантируется, что входные данные корректны, то есть:
В каждой строке целые числа разделены одиночными пробелами.
Выведите 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
Название |
---|