Динамическое sos dp с удалением и вставкой элементов за O(2^(k/2))

Revision ru2, by Peter-007, 2024-03-23 15:06:30

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

Основная идея здесь это применение meet-in-the-middle.

В наивном алгоритме, для вставки, или удаления, мы просто создадим вектор размера $$$2^k$$$, где $$$dp_{mask}$$$ означает количество элементов с данным значением, и просто сделаем $$$dp_{mask}++$$$ (либо $$$dp_{mask}--$$$), поэтому это зайтем $$$O(1)$$$ времени, и чтобы сделать запрос просто пробежимся по всем подмаскам of за $$$O(2^k)$$$. Довольно очевидно, что мы можем это сбалансировать.

Разделим биты пополам, для вставки, или удаления, мы пробежимся по всем надмаскам первой половины бит (назовем $$$maskup$$$) и добавим сюда вторую половину (назовем $$$masksec$$$), то есть сделаем $$$dp_{maskup+masksec}++$$$ (либо, если хотим удалить, отнимем единицу).

Чтобы сделать запрос, сделаем наоборот: первая половина зафиксирована, и мы пробежимся по всем подмаскам второй половины.

Единственная проблема это то, что у нас осталось $$$O(2^k)$$$ памяти, мы можем сделать map или unordered_map, но это довольно медленно, или по-умному использовать векторы.

Код (используя вектора с O(2^(k/2)) памяти)
Задача (некоторые другие решения, которые не используют данную идею, могут существовать)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian Peter-007 2024-03-23 15:07:31 4 Мелкая правка: 'ь тип $1$ to $k$ $(1 \' -> 'ь тип $1$ до $k$ $(1 \'
ru2 Russian Peter-007 2024-03-23 15:06:30 26 Мелкая правка: '_size; // sizes of parts\n vect' -> '_size; // размеры частей\n vect'
ru1 Russian Peter-007 2024-03-23 15:05:43 5681 Первая редакция перевода на Русский
en1 English Peter-007 2024-03-23 14:37:12 5702 Initial revision (published)