Существует ли структура данных, представляющая большой набор S
(64-разрядных) целых чисел, который начинается пустым и поддерживает следующие две операции:
-
insert(s)
вставляет числоS
вS
; -
minmod(m)
возвращает числоS
вS
так, чтоs mod m
минимально.
Пример:
insert(11) insert(15) minmod(7) -> the answer is 15 (which mod 7 = 1) insert(14) minmod(7) -> the answer is 14 (which mod 7 = 0) minmod(10) -> the answer is 11 (which mod 10 = 1)
Я заинтересован в минимизации максимального суммарного времени, затраченного на последовательность n
таких операций. Очевидно, что можно просто сохранить список элементов для S
и перебрать их для каждой операции minmod
; то вставка O(1)
, а minmod - O(|S|)
, что займет O(n^2)
время для операций n
(например, n/2
insert
, за которыми следуют операции n/2
minmod
, будет примерно грубо n^2/4
операции).
Итак: возможно ли сделать лучше, чем O(n^2)
для последовательности операций n
? Может быть, O(n sqrt(n))
или O(n log(n))
? Если это возможно, мне также будет интересно узнать, есть ли структуры данных, которые дополнительно допускают удаление отдельных элементов из S
или удаление всех номеров в пределах интервала.