Easy Peasy, Lemon Squeezy 2

Prerequisites: Binary Indexed Tree/ Policy Based Data Structure/ Merge sort

Explanation: This is a code for insertion sort. You have to count the number of swaps required to sort the array $A$ in non-decreasing order. This can be easily done using Binary Indexed Tree/ Policy Based Data Structure/Merge sort.

Binary Indexed Tree/Policy Based Data Structure: Count number of pairs $(i,j)$ such that $A_i >A_j$where, $1\leq i< j\leq N$

Merge Sort: Count number of swaps required during sorting the two halves and merging them.

Time Complexity: $O(NlogN)$

Solution:

Setter’s solution (using BIT): https://ideone.com/KG82oX

Alter’s solution (using PBDS): https://ideone.com/Wav3uC