# Policy-Based Data Structures

Are you facing difficulties in solving ** Inversion Count** related coding problems? Then my Today’s blog is for you! Keep reading :)

First, let me give a brief intro. **Inversion Count** for an array indicates — how far (or close) the array is from being sorted. If the array is already sorted then the **Inversion count** is 0.Let us take an example of an array, arr = {8, 4, 2, 1}. Given array has six inversions:

(8,4), (4,2), (8,2), (8,1), (4,1), (2,1). This means two elements form an inversion if **i<j **and **a[i]>a[j]. **So the basic approach that you will be thinking would be using Merge Sort, but the good thing is we can easily do this in C++ using Policy-Based Data Structures(PBDS). The PBDS provides the programmer a high-performance, semantic safety and flexibility as compared to the standard **data structures** of the C++ std library.

It works similarly as Sets. It has two other functionalities which make it better (which is going to solve our Inversion count problem):

**find_by_order(k):**It returns the iterator pointing towards the kth largest element(starting from 0).**order_of_key(k):**It returns the number of elements in the set which are strictly less than K.This will take O(log(n)) time complexity.

So, by using find_by_order(k) functionality, iterate over each element in the array, and also, insert it in a stack. It will give the number of elements strictly less than K.But we want, a number of elements greater than K, so subtract find_by_order(i) from present stack size. Hence you will get the inversion count.

To know more about PBDS, Refer to this.