INVUSTP - Editorial


Practice Contest

Author: @praveen3277
Tester: @aneesh2312, @eccentrik, @hellb0y_suru
Editorialist: @praveen3277




Segment Tree


We are given a permutation of first N natural number in an array A and we are required to find the sum of inversions of each elements in the indices range [ L, R ].


Let us say that we are given this permutation A as { a1, a2, . . . , aN } where each element occurs from 1 to N exactly once, i.e, all elements are distinct. Then to find the sum of inversions in range [ L, R ] first we need to find inversions of each of the elements at each index.

And this we can do using bits in segment tree.

Now let us say that we have found the inversions of the elements at each index as { i1, i2, i3, . . . iN } and using this we can build another segment tree for range sum and then process the query.

The time complexity is O ( nlogn ).

And we are done.


Setter and Editorialist Solution:

Tester Solution 1:

@aneesh2312 Solution:

Tester Solution 2:

@eccentrik Solution:

Tester Solution 3:

@hellb0y_suru Solution:

PS: I tried to explain it in a simple way.Hope you enjoyed solving this problem in Code Chronicles 2.0. And sorry for my bad English.

Thank You :blush:


Correct me if Iā€™m wrong
We need to find the count of all the inversions of elements in L to R
5 4 3 2 1
query -> 2 3
answer to this query is 1, am I right?

1 Like

No! You have to find the sum of inversions of each element at L, L+1,L+2.....,R.
In the case of 5, 4, 3, 2, 1
query -> 2,3
answer = 1+2=3


1 Like