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

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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

Основная идея здесь это применение 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)) памяти)

struct mitm_sos
{
    int l_size, r_size; // размеры частей
    vector<vector<int> >a; // делим вектор размера 2^k на 2^(k/2) векторов размера 2^(k/2)
    vector<vector<pair<int, int> > >push_val; //временный вектор для пуша запросов
    //Основная идея оптимизации памяти к O(2^(k/2)) это делать resize a[left_part] только когда к нам пришел запрос
    //Когда мы делаем удаление, либо добавление, мы просто пушим в какой-то временный вектор push_val[left_part]
    mitm_sos(int k)
    {
        l_size = k / 2, r_size = k - l_size;
        //деление бит пополам
        a.resize(1 << l_size);
        push_val.resize(1 << l_size);
        //resize векторов
    }
    void insert(int x)
    {
        int left_part = x & ((1 << l_size) - 1), right_part = ((x - left_part) >> l_size);
        for(int mask = 0; mask < (1 << l_size); mask++)
            if((mask & left_part) == left_part)
                push_val[mask].push_back({right_part, 1});
                //для каждой надмаски левой части добавить правую
                //Вместо того, чтобы добавлять это к какому-то вектору размера 2^k, мы пушим во временный вектор
    }
    void erase(int x)
    {
        //Эта функция такая же, как и вставка, но мы добавляем -1, а не 1
        int left_part=x & ((1 << l_size) - 1), right_part = ((x - left_part) >> l_size);
        for(int mask = 0; mask < (1 << l_size); mask++)
            if((mask & left_part) == left_part)
                push_val[mask].push_back({right_part, -1});
    }
    int sos_sum(int x)
    {
        int ans = 0;
        int left_part = x & ((1 << l_size) - 1), right_part = ((x - left_part) >> l_size);
        if(a[left_part].size() == 0)a[left_part].resize(1 << r_size); //если к этой левой части еще не было запроса
        for(auto &x : push_val[left_part])a[left_part][x.first] += x.second; //пушим все, что не добавлено
        push_val[left_part].clear();
        for(int mask = 0; mask < (1 << r_size); mask++)
            if((mask & right_part) == mask)
              ans+=a[left_part][mask];
              //пробегаемся по правой части
        return ans;
    }
};

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

Дано дерево с $$$n$$$ вершинами $$$(1 \le n \le 5*10^4)$$$, где у каждого ребра есть тип $$$1$$$ до $$$k$$$ $$$(1 \le k \le 15)$$$. Скажем, что путь от вершины $$$u$$$ до вершины $$$v$$$ хороший, если на данном пути можно найти все типы ребер.

Посчитать количество хороших путей по всем $$$\frac{n(n+1)}{2}$$$. TL 2.5s.

Мое решение (длиннее, чем весь остальной блог)

Заметим, что можно хранить маски для типов ребер, которые мы видели. Пройти по ребру типа $$$c$$$ то же, что и сделать $$$mask$$$ |= $$$2^c$$$. Тогда путь хороший при условии $$$mask = 2^k-1$$$.

Для решения можно использовать small-to-large или центроидную декомпозиции. Я буду использовать small-to-large, но это не важно.

В структуре для small-to-large будем держать вектор размера $$$2^k$$$, где будем хранить сколько раз мы видели маску. Если мы хотим вставить новую вершину из другого поддерева, тогда пробежимся по всем $$$2^k$$$ маскам и если $$$mask|mask2=2^k-1$$$ добавим к ответу $$$amount_{mask2}$$$, где $$$mask2$$$ это величина, по которой пробегаемся. После этого сделаем $$$amount_{mask}++$$$.

Чтобы пройти по ребру для всех масок сделаем $$$newamount_{mask|2^c}+=amount_{mask}$$$.

Это решение работает $$$O(n*2^k*logn)$$$ времени.

Попробуем оптимизировать. Если присмотреться, для фиксированной маски $$$mask$$$, $$$mask2$$$ которые делают хорошие пути ($$$mask|mask2=2^k-1$$$), образуют какое-то подмножество (на самом деле сумма надмножества $$$2^k-1-mask2$$$). Давайте поддерживать наш динамический SOS дп в структуре small-to-large. Если мы хотим вставить новую вершину из другого поддерева, сделаем запрос за $$$O(2^{k/2})$$$, и после этого вставим новую величину тоже за $$$O(2^{k/2})$$$.

Но мы все еще не можем пройти по ребру. Чтобы это сделать, заметим, что для фиксированной вершины, когда мы поднимаемся наверх, ее маска изменится не более $$$k$$$ раз. Поэтому предпосчитаем это за $$$O(n*k*logn)$$$ бинарным поиском и бинарными подъемами. После этого запомним, когда нужно изменить маску. Для этого удалим старое значение из структуры и вставим новое.

Асимптотика $$$O(n(logn+k)*2^{k/2}$$$).

Блог пользователя Peter-007