Codeforces Round 893 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие между простой и сложной версиями в том, что в сложной версии вы должны отвечать на запросы в режиме онлайн. Вы можете делать взломы, только если обе версии задачи решены.
У вас есть массив $$$a$$$, изначально пустой. Вам нужно обрабатывать запросы следующих типов:
В первой строке задано одно целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — количество запросов.
В следующих $$$q$$$ строках даны запросы в формате, описанном выше.
Гарантируется, что
Также гарантируется, что количество запросов четвёртого вида (?) не превосходит $$$10^5$$$.
Обратите внимание, что вы должны решить данную задачу в режиме онлайн. То есть вы не можете считать все входные данные заранее. Вы можете считать очередной запрос только после того как выведете ответ на предыдущий, поэтому не забывайте сбрасывать поток вывода после вывода ответа. Вы можете использовать такие функции как fflush(stdout) в C++, BufferedWriter.flush в Java или похожие после каждого вывода в программе.
Для каждого запроса четвёртого типа выведите одно целое число: количество различных элементов в массиве $$$a$$$ в момент запроса.
10 + 1 + 2 + 2 ? ! + 3 - 2 ? + 1 ?
2 1 1
6 + 1 + 1000000 ? ! ! ?
2 0
В первом тесте из условия массив $$$a$$$ изменяется следующим образом:
Во втором тесте из условия массив $$$a$$$ изменяется следующим образом:
Название |
---|