Редактируем Зингер | color
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, *special

Немногие знают, что сотрудники ВКонтакте могут менять цвет подсветки в куполе знаменитого Дома Зингера, где расположена штаб-квартира ВКонтакте. Для этого нужно всего лишь отправить сообщение с цветом в специальный чат «Зингер | color», а бот его распознает и сменит подсветку. При этом на время городских мероприятий смена цвета блокируется.

Формально, бот обрабатывает три типа сообщений:

- lock: заблокировать изменение цвета. Если оно и так заблокировано на данный момент, сообщение игнорируется.
- unlock: разблокировать изменение цвета. Если оно и так разблокировано на данный момент, сообщение игнорируется.
- red / orange / yellow / green / blue / indigo / violet: изменить цвет купола на заданный, если изменение цвета на данный момент не заблокировано.

Вам дана история сообщений, полученных ботом, в хронологическом порядке. Считайте, что перед получением первого сообщения купол подсвечивается голубым (blue), а изменение цвета не заблокировано.

В качестве эксперимента было решено поддержать в боте эффективную обработку редактирования сообщений. Вам дана последовательность пар вида $$$(i, msg)$$$, означающих, что $$$i$$$-е в хронологическом порядке сообщение было отредактировано и теперь имеет вид $$$msg$$$. Обратите внимание, что редактироваться может любое сообщение, и при редактировании сообщения бот должен обработать всю историю сообщений заново (в частности, перед обработкой первого сообщения цвет купола голубой, а изменение цвета не заблокировано).

Определите, какой цвет будет у купола Дома Зингера до первой операции редактирования, а также после каждой операции редактирования.

Input format:
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число сообщений, полученных ботом.

В следующих $$$n$$$ строках заданы сообщения, полученные ботом, в хронологическом порядке, по одному сообщению в строке. Каждое сообщение — строка из следующего набора: lock, unlock, red, orange, yellow, green, blue, indigo, violet. Сообщения пронумерованы от $$$1$$$ до $$$n$$$.

В следующей строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — число операций редактирования сообщений.

В следующих $$$t$$$ строках заданы операции редактирования в хронологическом порядке, по одной в строке. Каждая операция — пара из номера сообщения $$$i$$$ ($$$1 \le i \le n$$$) и его нового содержимого $$$msg$$$, также принадлежащего набору lock, unlock, red, orange, yellow, green, blue, indigo, violet.

Output format:
Выведите $$$t+1$$$ строку: цвет купола до первой операции редактирования, а также после каждой операции редактирования в хронологическом порядке.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
7
red
violet
unlock
red
orange
lock
indigo
6
5 green
6 lock
6 yellow
4 lock
1 lock
5 unlock

Example output:
orange
green
green
indigo
violet
blue
indigo

Example input:
1
red
8
1 lock
1 unlock
1 blue
1 unlock
1 unlock
1 lock
1 yellow
1 lock

Example output:
red
blue
blue
blue
blue
blue
blue
yellow
blue

Editorial:
Если после каждой операции редактирования заново проходить по всей истории сообщений, сложность составит $$$O(tn)$$$ и решение не уложится в лимит времени. Рассмотрим более эффективный подход.
Для простоты добавим в начало хронологии сообщения unlock и blue, которые никогда не будут редактироваться, а в конец — сообщение lock.
Назовём сообщение unlock полезным, если следующее после него в хронологическом порядке сообщение содержит цвет. Можно заметить, что меняют цвет купола те и только те «цветные» сообщения, которые идут подряд непосредственно после полезных unlock'ов. Основываясь на этом факте, можно определить итоговый цвет купола так:
1. Найти последний полезный unlock. Обозначим его позицию через $$$p$$$. (Хотя бы один полезный unlock существует, так как мы добавили в начало сообщения unlock и blue.)
2. Найти следующий после позиции $$$p$$$ lock или unlock. Обозначим его позицию через $$$q$$$.
3. Сообщение $$$q-1$$$ содержит искомый цвет.
Будем поддерживать два упорядоченных множества — множество $$$a$$$, содержащее позиции всех полезных unlock'ов, и множество $$$b$$$, содержащее позиции всех lock'ов и unlock'ов вместе взятых.
После редактирования сообщения $$$i$$$ нужно добавить в множества или удалить из них только позиции $$$i$$$ и $$$i-1$$$, а затем определить новый цвет купола по описанной выше последовательности действий. Соответственно, всего нужно выполнить $$$O(1)$$$ операций с множествами.
От множеств нам нужно эффективное выполнение операций добавления, удаления, поиска, взятия максимального элемента, и взятия следующего в отсортированном порядке элемента. С этим справится любое сбалансированное дерево поиска. Можно воспользоваться встроенными во многие языки структурами данных: например, в C++ подойдёт std::set, в Java — TreeSet. Такие структуры выполняют требуемые операции за $$$O(\log n)$$$.
Итоговая сложность решения составляет $$$O(t \log n)$$$.
Пример решения на C++: