может кто-нибудь помочь мне с этой задачей http://www.spoj.com/problems/INVCNT/ . Сначала я пытаюсь мыслить БИТ, но не могу. Может кто-нибудь объяснить решение этой задачи с помощью BIT. BIT- двоичное индексированное дерево
C ++
Предполагая, что вы знаете, как решить следующую проблему в 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.
Замечания: проблема также имеет изящное решение, используя Сортировка слиянием что вы можете подумать.
Других решений пока нет …