I was doing well with SPOJ Problems, but due to some Problems, I am stuck with them. I am in the first year of my BTECH, but I am pretty much confident with the Ad-Hoc Problems. I am new with Graph Theory. I want to learn it.
Problem Link is this
Some one please make me understand the Problem. I have read about Trees, but not so much helped. Someone please be kind and answer. Thanks in Advance! :)
I don't think this has anything to do with graphs. It's a variation of merge sort. ( Divide and conquer).
MedoN11 So How we will apply Divide and Conquer?
http://www.geeksforgeeks.org/counting-inversions/
Merge sort will do.I have also heard that this question can be done using Binary Indexed Trees.
Can you please make me understand how it will be done by Merge Sort? antivenom
Merge sort works by splitting the array in half, sorting those halves, and then merging them together. In that merge, whenever the current minimum element is on the second half, it will create inversions with all the remaining elements from the first half.
This is simple BIT problem.First add that number in BIT ( update position bit[a[i]]). For each position i you should find how many numbers left of it are bigger ( you find how many numbers are smaller or equal with BIT) and add on answer i-(that number). Also number should be long long ...