SPOJ INVCNT — как?

Предполагая, что вы знаете, как решить следующую проблему в O(log n) за запрос и обновление с использованием BIT:

Given an array A[1 .. n], implement the following functions efficiently:
query(x, y) = return A[x] + A[x+1] + ... + A[y]
update(x, v) = set A[x] = v

Вы можете решить свою текущую проблему следующим образом: сначала нормализуйте значения массива. Это означает, что вы должны преобразовать все свои значения так, чтобы они находились в интервале [1, n], Вы можете сделать это с помощью сортировки. Например, 5, 2, 8 станет 2, 1, 3, (Примечание: 1, 2, 3 — индексы в отсортированном порядке 5, 2, 8)

Тогда для каждого iответим сколько инверсий A[i] генерирует с элементами j < i, Для этого нам нужно найти количество элементов до i которые больше чем i, Это эквивалентно query(A[i] + 1, n),

После этого запроса мы делаем update(A[i], 1),

Вот как это работает: наш массив BIT будет изначально заполнен нулями. А 1 в положении k в этом массиве означает, что мы столкнулись со значением k в нашей итерации по данному массиву. По телефону query(A[i] + 1, n)находим сколько инверсий A[i] генерируется с элементами перед ним, потому что мы запрашиваем, сколько элементов больше, чем мы повторили до сих пор.

Найдя это, нам нужно отметить A[i] как посетил. Мы делаем это путем обновления позиции A[i] в нашем массиве BIT и положить 1 на него: update(A[i], 1),

Так как числа в массиве отличаются от 1 в n, ваш массив BIT имеет размер n и сложности являются логарифмическими в n,

Напишите, если вам нужны подробности о том, как решить начальную проблему, хотя это классика, и вы сможете легко найти код в Google.

Замечания: проблема также имеет изящное решение, используя Сортировка слиянием что вы можете подумать.