Олимпиадный тренинг

Задача . A. Тор


Задача

Темы: Перебор реализация Структуры данных *1600

Тор постепенно привыкает к жизни на земле. Недавно Локи подарил ему смартфон, на котором уже установлены n приложений. Тору очень нравится новый телефон, но ему не хватает информации о количестве непрочитанных оповещений от приложений (возможно, это Локи наложил на телефон проклятье, кто знает).

Последовательно произойдёт q событий, каждое из которых будет одного из трёх типов:

  1. Приложение x порождает новое оповещение (которое, разумеется, изначально не прочитано).
  2. Тор просматривает все оповещения от приложения x (в том числе перечитывает уже прочитанные).
  3. Тор просматривает первые t оповещений, сгенерированных какими-либо приложениями (то есть первые t событий первого типа). Гарантируется, что к этому моменту уже произошло хотя бы t событий первого типа. Обратите внимание, что Тор читает не первые t непросмотренных оповещений, а просто первые t оповещений, в том числе просматривая какие-то заново.

Помогите Тору определить количество непросмотренных оповещений после каждого события. Считайте, что изначально никаких оповещений в телефоне не было.

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

В первой строке входных данных записаны целые числа n и q (1 ≤ n, q ≤ 300 000) — количество приложений и количество событий соответственно.

Следующие q строк содержат описания событий, в i-й из них будет сначала записано целое число typei — тип события. Если typei = 1 или typei = 2, то далее следует целое число xi. А если typei = 3, то далее следует целое число ti (1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ q).

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

Выведите количество непрочитанных оповещений после каждого события.

Примечание

В первом примере:

  1. Приложение 3 создаёт оповещение (количество непрочитанных оповещений равно 1).
  2. Приложение 1 создаёт оповещение (количество непрочитанных оповещений равно 2).
  3. Приложение 2 создаёт оповещение (количество непрочитанных оповещений равно 3).
  4. Тор читает все оповещения, созданные приложением 3, остаётся 2 непрочитанных оповещения.

Во втором примере:

  1. Приложение 2 создаёт оповещение (количество непрочитанных оповещений равно 1).
  2. Приложение 4 создаёт оповещение (количество непрочитанных оповещений равно 2).
  3. Приложение 2 создаёт оповещение (количество непрочитанных оповещений равно 3).
  4. Тор читает первые три оповещения, и непрочитанных оповещений становится 0.
  5. Приложение 3 создаёт оповещение (количество непрочитанных оповещений равно 1).
  6. Приложение 3 создаёт оповещение (количество непрочитанных оповещений равно 2).

Примеры
№Входные данныеВыходные данные
1 3 4
1 3
1 1
1 2
2 3 
1
2
3
2
2 4 6
1 2
1 4
1 2
3 3
1 3
1 3 
1
2
3
0
1
2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет