- Описание
- Отправленные решения
5. Бутерброды
Раньше Саша был олимпиадником, но из-за того, что он живет не в столице, а в небольшом городе К, он не смог на этом заработать денег, и теперь ему приходится работать поваром в студенческой столовой. Сейчас Саша занят составлением рецептов бутербродов, которые в будущем он планирует подавать на завтрак. Изначально перед ним лежит $K$ кусков хлеба и он совершает с ними $N$ последовательных операций, каждая из которых относится к одному из следующих типов:
Саша берет ингредиент $x$ из холодильника и кладет сверху на $i$-й бутерброд;
Саша снимает с $i$-го бутерброда верхний ингредиент и возвращает его в холодильник;
Саше начинает казаться, что $i$-й и $j$-й бутерброды слишком сильно отличаются по размеру, поэтому он начинает перекладывать ингредиенты с большего бутерброда на меньший, пока разница их размеров станет не больше, чем 1.
Требуется написать программу, которая выведет количество различных бутербродов, которые получались у Саши в ходе составления рецептов. Пустой бутерброд не считается бутербродом. Бутерброды, которые получаются в процессе выполнения операции третьего типа, также следует принимать во внимание.
Два бутерброда считаются различными, если у них различается число ингредиентов или их порядок (то есть существует такое $i$ что на $i$-м сверху месте расположены ингредиенты разного типа).
Формат ввода
В первой строке указаны два числа $K$ и $N$ ($K \leq 20$, $N \leq 3 \cdot 10^5$) $-$ количество кусков хлеба, лежащих перед Сашей и количество действий, соотвественно.
В последующих $N$ строках описаны действия, совершенные Сашей. Каждая строка начинается с числа $1$, $2$ или $3$, обознчающих тип операции. Если операция имеет тип $1$, то после написаны два целых числа $i$ и $x$ ($1 \le i \leq K$, $1 \le x \leq 10^9$) $-$ номер бутерброда и ингредиента, соотвественно. Для операции типа $2$ записано одно целое число $i$ ($1 \le i \leq K$) $-$ номер бутерброда. Гарантируется, что на этом бутерброде есть хотя бы один игредиент. Наконец, для операций типа $3$ записана пара целых чисел $i$ и $j$ ($1 \le i,j \le K$, $i \ne j$) $-$ номера бутербродов, которые надо «уравнять».
Формат вывода
Вывести требуется единственное число $-$ ответ на задачу.
Ограничения
Ограничение времени
2 с
Ограничение памяти
512 МБ
Пример 1
3 5
1 1 3
1 1 3
3 2 1
1 2 7
1 3 7
4