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

Задача . H. Ксюша и загруженное множество


Задача

Темы: Бинарный поиск Перебор реализация Структуры данных *2200

Ксюша решила основать компанию по производству игр. Чтобы выделиться среди конкурентов и добиться успеха, она решила написать свой игровой движок. Движок должен поддерживать множество, изначально состоящее из \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\).

К множеству будут последовательно применяться \(m\) операций. Операции бывают следующих типов:

  • Вставить элемент \(x\) в множество;
  • Удалить элемент \(x\) из множества;
  • Сообщить \(k\)-загруженность множества.

\(k\)-загруженностью множества называется такое минимальное целое положительное число \(d\), что числа \(d, d + 1, \ldots, d + (k - 1)\) не встречаются в этом множестве. Например, \(3\)-загруженность множества \(\{3, 4, 6, 11\}\) равна \(7\), так как числа \(7, 8, 9\) отсутствуют в множестве, а никакое меньшее значение не подходит.

Ксюша занята менеджерскими делами, поэтому движок придётся писать вам. Реализуйте эффективную поддержку описанных операций.

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

В первой строке дано целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Далее следуют описания наборов.

В первой строке дано целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — начальный размер множества.

Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_1 < a_2 < \ldots < a_n \le 2 \cdot 10^6\)) — начальное состояние множества.

В третьей строке дано целое число \(m\) (\(1 \le m \le 2 \cdot 10^5\)) — количество операций.

В следующих \(m\) строках даны операции. Операции даны в следующем формате:

  • + \(x\) (\(1 \le x \le 2 \cdot 10^6\)) — вставить элемент \(x\) в множество (гарантируется, что \(x\) отсутствует в множестве);
  • - \(x\) (\(1 \le x \le 2 \cdot 10^6\)) — удалить элемент \(x\) из множества (гарантируется, что \(x\) присутствует в множестве);
  • ? \(k\) (\(1 \le k \le 2 \cdot 10^6\)) — вывести значение \(k\)-загруженности множества.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\), то же самое гарантируется для \(m\).

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

Для каждого набора входных данных выведите ответы на операции типа «?».


Примеры
№Входные данныеВыходные данные
1 3
5
1 2 5 905 2000000
15
- 2
? 2
? 1
- 1
? 1
+ 4
+ 2
? 2
+ 6
- 4
+ 7
? 2
? 3
? 4
? 2000000
5
3 4 5 6 8
9
? 5
- 5
? 5
+ 1
? 2
- 6
- 8
+ 6
? 5
5
6 7 8 9 10
10
? 5
- 6
? 4
- 10
+ 5
- 8
+ 3
+ 2
- 3
+ 10 
2 2 1 6 3 8 8 2000001 
9 9 9 7 
1 1

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

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

Ваш ответ

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


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

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