CODESPTB I’ve solved this problem using brute force, since time limit is high it passes, I read someone’s comment stating it can be solved with policy based Data structure.
So, what is policy based DS and how can this be applied to this problem?
I’m came across a codeforces blog but couldn’t understand it.
PS:I googled didn’t find a solution using policy based DS.
This question can be solved simply by counting the number of inversions in an array . Inversions is basically the number of indices i and j such that i < j and a[i] > a[j]. This can be counted by adding one line to the code of the sorting algorith merge-sort. As merge-sort algorithm takes O(nlogn) time, the time complexity of this solution will be O(TNlogN) which is very fast as compared to the O(TN^2) brute force .
Here is my accepted submission of the question.
Another famous way to count the number of inversions in the array is to use Fenwick tree (also known as Binary Indexed Tree/ BIT). You can read about it here.
Thank You!