Given an array $$$a_1,a_2,\dots,a_n$$$, $$$a_i=i$$$ and a permutation of this array $$$p_1,p_2,\dots,p_n$$$. We sort this permutation to get initial array using bubble sort.

**Question:** how to calculate a number of swaps in $$$O(n)$$$ instead $$$O(n^2)$$$?

Count the inversions

Counting inversions would take O(nlogn).

Edit: my solution is wrong.

Yeah, Thanks for explaining.

Could you please share code?

I realized I made a wrong observation. So my solution would not work. Sorry about that.

In case you still haven't gotten your answer, the following takes $$$O(n \log n)$$$: perhaps the easiest way is to use a segment tree. First, initialize

`cnt=0`

. Process the array in order from left to right. When we get to a new element with value`x`

, do the operation`update(x,1)`

(add 1 to location`x`

in the tree). Then, query for the sum from one more than that element's value to the maximum value in the array, and add that to a running inversion count:`cnt += query(x+1, N)`

(where`N`

is the maximum possible value in the array). The answer is`cnt`

after you've processed the entire array.