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

Основная идея здесь это применение 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, но это довольно медленно, или по-умному использовать векторы.

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=200$$$ элементов, вам нужно перебрать все их возможные четверки, порядок элементов в каждой четверке не влияет, и можно взять один и тот же элемент несколько раз. Дайте быструю приближенную оценку количества итераций алгоритма.

Вчера на BSUIR Open мне встретилась такая задача: Дан массив $$$a$$$ из $$$n$$$ элементов и $$$q$$$ запросов:

1. Даны два числа $$$l,r,$$$ посчитать $$$\sum_i^{r-l+1} a_{l+i}*fib_i$$$ по модулю $$$10^9+7$$$, где $$$fib_i$$$ — $$$i$$$-тое число Фибоначчи.
2. Даны три числа $$$l,r,x$$$, прибавить $$$x$$$ на отрезке с $$$l$$$ по $$$r$$$.

Однако при решении я никак не учитывал свойств чисел Фибоначчи, и решал задачу в общем виде, чего мне не удалось, и теперь стало интересно, возможно ли её решить общую задачу за время, быстрее $$$O(nq)$$$ или доказать, что это невозможно?

Более формально: Дан массив $$$a$$$, а также массив $$$c$$$, оба из $$$n$$$ элементов и $$$q$$$ запросов:

1. Даны два числа $$$l,r,$$$ посчитать $$$\sum_i^{r-l+1} a_{l+i}*c_i$$$ по модулю $$$10^9+7$$$.
2. Даны три числа $$$l,r,x$$$, прибавить $$$x$$$ на отрезке с $$$l$$$ по $$$r$$$.

Можете помочь?

I started codeforces nearly a month ago and recently got a question: how to "actually" sort problems by difficulty?

I understand that difficulty is subjective, but for an average Codeforces user some problems of the same Codeforces difficulty still would be much much harder than others. And sorting by Codeforces difficulty and looking for the problem with average amount of solves doesn't help either, since older problems have less solves, because Codeforces was less popular.