Изменения

Для построения таблицы инверсий за линейное время воспользуемся карманной сортировкой. Известно что карманная сортировка имеет линейную сложность, но только в том случае если элементы равномерно распределены. Т.к. мы ищем кол-во инверсий в перестановке то мы знаем что наши элементы встречаются единожды , а следовательно равномерно распределены. При карманной сортировке нужно определить карман '''<tex>B'''</tex>, в который попадет текущий элемент. Затем найти количество элементов в старших карманах относительно '''<tex>B'''</tex>. Потом аккуратно подсчитать количество элементов, больших текущего в кармане '''<tex>B'''</tex>. Карман '''<tex>A''' </tex> считается старшим для кармана '''<tex>B'''</tex>, если любой элемент из '''<tex>A''' </tex> больше любого элемента из '''<tex>B'''</tex>.

<font color=green>MAX - число больше a.size() и из которого можно извлечь целый квадратный корень.</font>

'''int''' bucket_sort( '''vector<int>''' a ): '''int''' ans = 0;<font color=green>//изначально кол-во инверсий</font> '''vector<int>''' tab_invers(a'''.size()'''+1);<font color=green>//таблица перестановок</font> '''vector< list<int> >''' mem(BUCKET); '''for'''('''int''' i = 0;i < a'''.size()''' ; i++) '''int''' invers = 0; <font color=green>//кол-во инверсий которые создает элемент a[i]</font> '''int''' pos = (a[i] - 1)/(MAX / BUCKET);<font color=green>//Определяем в каком кармане должен лежать элемент</font> '''list<int>::iterator''' it = mem[pos]'''.begin()'''; '''int''' newpos = 0; '''while'''(it != mem[pos]'''.end()''' && (*it) < a[i] ) <font color=green>//идем до позиции где должен стоять элемент</font> it++; newpos++; invers += mem[pos]'''.size()''' - newpos;<font color=green>//ищем сколько инверсий эленент создает в своем кармане</font> mem[pos]'''.insert'''( it , a[i] );<font color=green>//вставляем элемент в список</font> '''for'''('''int''' i = pos + 1 ; i < BUCKET ; i++) <font color=green>//ищем сколько инверсий он создает с элементами в других карманах</font> invers += mem[i]'''.size()'''; tab_invers[a[i]] = invers; ans += invers; '''return''' tab_invers; '''return''' ans;

Утверждается, что cложность Сложность представленного алгоритма есть <tex>O(n)</tex>.