@Anshu:
My logic:
during merge step, lets say you have two array left and right (both are
sorted) and you are going to merge it.
l[i] represent the element of left arrray
r[j] represent the element of right array
if (r[j] < l[i]) {
increase the inversion count by the number of elements lefts in left array
put element r[j] into merged array
j++
} else {
no increase in count, just put the element r[i] into merged array
i++;
This will be O(nlogn) solution. Can we do better using BIT or segment trees?
Can you please provide me some hint of how to solve it using segment trees,
I just know the basics of it..
On Thu, May 12, 2011 at 5:00 PM, anshu mishra <[email protected]>wrote:
> explain your logic instead of posting code, use binary index tree or
> segment tree or bst to solve this problem.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
