PROBLEM-LINK
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:
Tester Solution 1:
@aneesh2312 Solution: CodeChef: Practical coding for everyone
Tester Solution 2:
@eccentrik Solution: CodeChef: Practical coding for everyone
Tester Solution 3:
@hellb0y_suru Solution: CodeChef: Practical coding for everyone
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 