Блог

Я пытаюсь решить проблему, которая определяется следующим образом:

Конфета представлена числом от 1 до 1e6. Говорят, что у человека есть набор из k конфет, если у него есть конфета от 1 до k.

Например. Если человек купил конфеты 1, 2 и 6, то у него есть набор из 2 конфет

Задано 2 типа операций: Съесть x и купить x, где x представляет количество конфет. Покупка x увеличит количество x только на 1. Съеденное x уменьшит количество x только на 1.

Для каждой операции ответьте на вопрос, каков размер набора конфет, который у меня есть сейчас?

Я пытаюсь найти наиболее эффективный способ сделать это. Решение, о котором я подумал, описано ниже:

Пусть count[i] определяет массив размером 1 — N, где N — максимально возможное количество конфет. count[i] хранит количество конфет с номером i, которое у меня есть на данный момент.

Пусть массив Fenwick [i] размером 1 — N, где N — максимально возможное количество конфет. Этот массив предназначен для построения дерева Фенвика для хранения совокупных сумм конфет в моей коллекции. Эта совокупная сумма не использует массив count. Совокупная сумма учитывает количество в 1s (каждая 1 указывает, что в моей коллекции присутствует конфета x). например, если у меня есть набор из 5 конфет, то совокупная сумма от 1 до 5 равна 5. если есть набор из 10 конфет, то совокупная сумма от 1 до 10 равна 10…

Для операции покупки, если конфет x еще не было в моей коллекции, добавьте 1 к совокупной сумме, начиная с индекса x (это обрабатывается деревом Фенвика). В противном случае я просто выполню count [x]

Для операции съедания выполните count[x]— . Если count [x] теперь равен 0, то я уменьшаю 1 от совокупной суммы, начиная с индекса x (это обрабатывается деревом Фенвика).

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

Я попытался запросить в дереве Фенвика наибольший индекс, i, для которого совокупная сумма от 1 до i равна i, при этом каждый раз увеличивая индекс моего запроса в степени 2.

Я беру наибольший индекс, который является допустимым набором конфет, j, и наименьший индекс, который является недопустимым набором конфет, k. Затем выполните цикл от j до k, запрашивая дерево фенвика на каждой итерации. Как только цикл попадет в недопустимую коллекцию, прервите и выведите ответ.

Мне кажется, что это сработало бы. Однако это, безусловно, не эффективный метод. Кто-нибудь может просветить меня о лучшем решении? Заранее спасибо.

редактировать (решение):

Мой подход к вставке и удалению был правильным. Просто я искал коллекцию конфет неправильным способом. В этом случае нам нужно наибольшее число x, где запрос (x) = x (запрос (x) выдает совокупную сумму от 1 до x). Таким образом, мы можем использовать двоичный поиск, чтобы найти наибольшее допустимое значение x (query (x) = x). Для достижения этого нам просто нужно сохранить дополнительную переменную для отслеживания последнего значения x, где query (x) выдает допустимую коллекцию.

Сложность решения: O (log^ 2(N))

Обычно это двоичная древовидная структура.

Для простоты предположим, что индексы конфет варьируются от 0 до 2^k - 1 некоторого целого k числа. Затем в каждый момент времени статус представляется 16 числами, c[0] до c[2^k - 1] , где c[i] — количество конфет i .

Мы строим двоичное дерево следующим образом: корневой узел P(0, 2^k) представляет весь интервал [0, 2^k) ; Для каждого узла, P(a, b) такого, что b - a > 1 , постройте два подузла P(a, (a b)/2) и P((a b)/2, b) .

Пусть p(a, b) будет минимум c[i] для i в интервале [a, b) . По-видимому, мы имеем:

• p(a, a 1) = c[a] ;

• p(a, b) = min{p(a, (a b)/2), p((a b)/2, b)} если b - a > 1 .

Построив эту структуру данных, для каждой операции (плюс один или минус один) мы можем обновлять данные O(k) поэтапно, снизу вверх. Более того, определение размера набора конфет также может быть выполнено в O(k) шагах.

Пример структуры данных:

Давайте рассмотрим случай k = 3 , чтобы c[0] было c[7] . Например:

c[0 .. 7] = {1, 3, 0, 4, 3, 2, 8, 1}

Тогда древовидная структура выглядит следующим образом:

 p(0, 8) = 0
|- p(0, 4) = 0
|  |- p(0, 2) = 1
|  |  |- p(0, 1) = 1
|  |  |_ p(1, 2) = 3
|  |_ p(2, 4) = 0
|     |- p(2, 3) = 0
|     |_ p(3, 4) = 4
|_ p(4, 8) = 1
   |- p(4, 6) = 2
   |  |- p(4, 5) = 3
   |  |_ p(5, 6) = 2
   |_ p(6, 8) = 1
      |- p(6, 7) = 8
      |_ p(7, 8) = 1
  

Теперь предположим, что мы прибавляем 1 к числу c[2] , которое получается 1 , затем нам нужно только обновить числа p(2, 3) , p(2, 4) p(0, 4) , p(0, 8) ,,,,,,,,,,,,,,,.