INVUSTP - Editorial

PROBLEM-LINK

Practice Contest
Contest

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

DIFFICULTY

Easy-Medium

PREREQUISITES

Segment Tree

PROBLEM

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 ].

EXPLANATION

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.

SOLUTIONS

Setter and Editorialist Solution:

https://www.codechef.com/viewsolution/36592901

Tester Solution 1:

@aneesh2312 Solution: https://www.codechef.com/viewsolution/36593011

Tester Solution 2:

@eccentrik Solution: https://www.codechef.com/viewsolution/36593046

Tester Solution 3:

@hellb0y_suru Solution: https://www.codechef.com/viewsolution/36593080

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:

4 Likes

Correct me if Iā€™m wrong
We need to find the count of all the inversions of elements in L to R
e.g.
5
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

dammit!

1 Like