В: Можно ли считать пары массивов с побитовым И > k ~ лучше, чем O(N^2)?

Пусть size_of_input_array = N. Пусть входной массив состоит из B-битных чисел

Вот простое для понимания и реализации решение.

• Удалите все значения <= k.

• На изображении выше показаны 5 10-битных чисел.

Шаг 1: График смежности

• Сохраните список установленных битов. В нашем примере 7-й бит установлен для чисел с индексами 0,1,2,3 во входном массиве.

Шаг 2: Задача состоит в том, чтобы избежать повторного подсчета одних и тех же пар.

Чтобы решить эту проблему, мы воспользуемся структурой данных union-find, как показано в коде ниже.

//unordered_map<int, vector<int>> adjacency_graph;
//adjacency_graph has been filled up in step 1

vector<int> parent;
for(int i = 0; i < input_array.size(); i++)
    parent.push_back(i);

int result = 0;
for(int i = 0; i < adjacency_graph.size(); i++){ // loop 1
    auto v = adjacency_graph[i];
    if (v.size() > 1){
        int different_parents = 1;
        for (int j = 1; j < v.size(); j++) { // loop 2
            int x = find(parent, v[j]);
            int y = find(parent, v[j - 1]);
            if (x != y) {
                different_parents++;
                union(parent, x, y);
            }
        }
        result += (different_parents * (different_parents - 1)) / 2;
    }
}
return result;

В приведенном выше коде find и union взяты из структуры данных union-find.

Сложность времени:

Шаг 1:

Build Adjacency Graph: O(BN)

Шаг 2:

Loop 1: O(B)
Loop 2: O(N * Inverse of Ackermann’s function which is an extremely slow-growing function) 

Общая временная сложность

= O(BN)

Космическая сложность

Overall space complexity = O(BN)

Во-первых, обрезать все <= k. Также отсортируйте список значений.

Переходя от старшего бита к младшему, мы собираемся отслеживать набор чисел, с которыми мы работаем (изначально все s=0, e=n).

Пусть p будет первой позицией, содержащей 1 в текущем наборе в текущей позиции.

Если бит в k равен 0, то все, что дает 1 мир, определенно будет хорошим, и нам нужно исследовать те, которые получают 0. У нас есть (end - p) * (end-p-1) /2 пар в текущем диапазоне и (end-p) * <total 1s in this position larger or equal to end> комбинаций с большими ранее хорошими числами, которые мы можно добавить в решение. Для продолжения обновляем end = p. Мы хотим посчитать единицы во всех приведенных выше числах, потому что раньше мы считали их только парами друг с другом, а не с такими младшими числами в наборе.

Если бит в k равен 1, то мы еще не можем подсчитать выигрыши, но нам нужно исключить все, что ниже p, поэтому мы обновляем start = p.

Вы можете остановиться, как только вы прошли все биты или start==end.

Подробности:

• Поскольку на каждом шаге мы удаляем либо все, что имеет 0, либо все, что имеет 1, то все между началом и концом будет иметь один и тот же битовый префикс. поскольку значения отсортированы, мы можем выполнить бинарный поиск, чтобы найти p.
• Для <total 1s in this position larger than p>. У нас уже есть отсортированные значения. Таким образом, мы можем вычислить частичные суммы и сохранить для каждой позиции в отсортированном списке количество единиц в каждой битовой позиции для всех чисел над ней.

Сложность:

• Мы получили побитно, поэтому L (битовая длина чисел), мы выполняем двоичный поиск (logN), а также поиск и обновление O (1), так что это O (L logN).
• Нам нужно отсортировать O(NlogN).
• Нам нужно вычислить частичные побитовые суммы O(L*N).

Всего O(L logN + NlogN + L*N).

Поскольку N>>L, L logN включается в NlogN. Поскольку L>>logN (вероятно, у вас есть 32-битные числа, но их не 4 миллиарда), то NlogN включается в L*N. Таким образом, сложность составляет O (L * N). Поскольку нам также нужно сохранять частичные суммы вокруг памяти, сложность также составляет O (L * N).