Вот решение по времени O(R log R) и пробелу O(R), где R - количество выбывших (снятых) игроков.Если вышедшим на пенсию игрокам дается в порядке возрастания идентификатора, то ваше последнее понимание правильное: вы можете просто прочитать идентификаторы и вспомнить их во времени O(R) и O(1) памяти.Это помогает, когда N намного больше, чем R (например, миллиарды), потому что это исключает сохранение любого массива размером N.
Концептуально идентификаторы вышедших на пенсию игроков - это листья в дереве.Вот дерево для N = 8. Я вычел 1 из всех идентификаторов, потому что это оказалось проблемой взлома, и хакеры любят считать от 0.: -)
0-7
/ \
0-3 4-7
/ \ / \
0-1 2-3 4-5 6-7
/ \ / \ / \ / \
0 1 2 3 4 5 6 7
Идея состоит в том, чтобыпосмотрите на компактные диапазоны во входных данных и выясните, сколько байсов они дают.Например, диапазон [0-3] дает один пока: ни одной игры в левой скобке (поддереве) не ведется, и тот, кто достигает финала из диапазона [4-7], получает прощание в финале.То же самое касается диапазона [4-7].По сути, если один диапазон покрывает одно полное поддерево, это один пока.Обратите внимание, что мы ищем максимально полные поддеревья, например, [0-3], а не [0-1] + [2-3] отдельно.
Как насчет [0-4]?Нам нужно разделить диапазон на [0-3] и [4-4].Тогда [4-4] является вторым поддеревом (тривиальным с одним узлом), то есть игрок 5 также получит прощай.Таким образом, [0-4] считается как два байса.Мы определяем это путем подсчета битов в количестве 5 (размер диапазона).Так как 5 = 101 2 , мы получаем ответ 2. Это часть битового взлома, которую я замаскирую, но могу расширить при необходимости.
Последний вопрос, который нужно рассмотреть, - ограничениеразмер диапазона.Пусть N=1024 и рассмотрим диапазон [4-100].Начиная с 4, поддерево заполняется до 7, и в этот момент мы должны обработать диапазон [4-7] (и получить 1 пока), а затем продолжить с 8 (это поддерево, в свою очередь, заполнится на 15 и т. Д.).Вычисление правильного конца также включает в себя немного взломать.Рассмотрим начальную точку 40 = 101000 2 .Размер поддерева задается младшим значащим битом, а именно 1000 2 = 8, поэтому мы должны пробиться после диапазона [40-47].Опять же, я замаскирую детали, но могу расширить при необходимости.
Код на C оказывается довольно коротким (извинения за то, что я не писал на Java, это было давно).Для краткости он подсчитывает биты с помощью встроенной функции *1029* в GCC, но есть множество других доступных методов.Аналогично, ограничение размера диапазона включает нахождение самого правого установленного бита .
#include <stdio.h>
void startRange(unsigned p, unsigned* start, unsigned* end, unsigned* limit) {
*start = *end = p;
*limit = p + (p & -p) - 1;
printf("started range %u limit %u\n", p, *limit);
}
int processRange(unsigned start, unsigned end) {
printf("processing range [%u,%u]\n", start, end);
return __builtin_popcount(end - start + 1);
}
int main() {
unsigned n, r, p, result;
unsigned start, end, limit;
/* read from standard input */
scanf("%d%d%d", &n, &r, &p);
startRange(p - 1, &start, &end, &limit);
result = 0;
while (--r) { /* read r-1 more numbers */
scanf("%d", &p);
p--;
if (p == end + 1 && p <= limit) {
/* continue while we have consecutive numbers, but not past the limit */
end++;
} else {
/* close the previous range and start a new one at p */
result += processRange(start, end);
startRange(p, &start, &end, &limit);
}
}
/* close any outstanding range we have */
result += processRange(start, end);
printf("%d\n", result);
return 0;
}