Sherlock and Inversion (with merge sort tree)

Revision en1, by Hasnaine_, 2018-06-09 20:13:01

Problem Link: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/sherlock-and-inversions/description/

The problem is about counting the number of inversion in a particular range(from L to R).

My approach: I used Mo's Algorithm here. And to calculate the add and remove function I used Merge Sort Tree. I was pretty sure it will pass the dataset of 5s. But somehow it gave TLE. Maybe miscalculated the complexity.

There is few solution available in the internet where I saw every of them solved it using Binary Indexed Tree. So, my question here is, if the problem will be solved using Merge Sort Tree or not after any kind of optimization. Or should I definitely use BIT. And if i do have to use BIT, then why?

My code: https://ideone.com/wPb0AC (You can skip the code though)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hasnaine_ 2018-06-09 20:13:01 917 Initial revision (published)