Вам дан список
из q (1 ≤ q ≤ 100000) команд.
По команде
"insert n" следует добавить n в набор чисел (повторы чисел допускаются).
По команде
"print" следует вывести XOR сумму наибольших k (1 ≤ k ≤ q) элементов
списка (если список содержит меньше k
элементов, то вывести XOR сумму всех элементов списка).
XOR сумма набора
чисел представляет собой выполнение операции XOR над ими всеми. XOR применяется
к двум целым числам, используя оператор ^ во многих языках программирования или
xor в Хаскеле (Паскале)).
Функция XOR
имеет несколько важных свойств. Например, если n ^ m = x, то n = x ^ m и m
= x ^ n.
Вход. Первая строка
содержит количество тестов t (1
≤ t ≤ 30). Каждый тест
начинается строкой, содержащей два целых числа q и k (1 ≤ q, k
≤ 100000). Каждая из следующих q
строк содержит одну команду.
Команды бывают двух видов:
insert n
или
print
n -
неотрицательное число, меньшее 231.
Выход. Для каждой
команды print вывести XOR сумму (не больше) k
наибольших элементов в текущем списке. Помните, что список очищается после
обработки каждого теста.
|
Пример
входа |
Пример
выхода |
|
1 5 2 insert 1 insert 2 print insert 3 print |
3 1 |
структуры
данных – куча
В задаче имеется
команда добавления элемента, но нет операции удаления. Значит если некоторый
элемент в какой-то момент времени перестал входить в k наибольших, то он уже никогда и не войдет в это множество (то
есть его можно выбросить из рассмотрения в дальнейшем).
В структуре
данных куча будем сохранять элементы, поступающие по команде insert.
Это будет min-куча, то есть на
вершине будет находиться минимальный элемент.
В переменной xor будем вычислять XOR поступающих на
вход элементов. При обработке команды print следует удалить все элементы,
не входящие в k максимальных, при
этом поддерживая в переменной xr
значение, равное XOR оставшихся в куче чисел.
Объявим min–кучу.
priority_queue<long long, vector<long long>,
greater<long long>
> pq;
Последовательно
обрабатываем test тестов.
scanf("%lld",&test);
while(test --)
{
cin >> q >> k;
Перед обработкой очередного теста
чистим кучу, обнуляем значение переменной xr.
xr = 0; while(pq.size()
> 0) pq.pop();
for(i = 0; i
< q; i++)
{
cin >> command;
При поступлении команды insert
заносим число n в кучу, обновляем
переменную xr.
if (command == "insert")
{
cin >> n;
xr ^= n;
pq.push(n);
}
else
{
Удаляем все числа, не входящие в k максимальных, пересчитывая xr. Метод pop удаляет
наименьшее число из кучи.
while(pq.size()
> k)
{
xr ^= pq.top();
pq.pop();
}
Выводим XOR сумму наибольших k элементов списка.
cout << xr << endl;
}
}
}