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)
Operations on mergesort tree are O(log2N) (with a generally not bad constant). Using Mo's, total complexity becomes O(N3 / 2log2N), so with N, Q = 105 you can expect 8.7 × 109 operations, which is quite unlikely to get AC :(