INVCNT  Inversion Count
Let A[0...n  1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.
Input
The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i  1] is given (A[i  1] <= 10^7). The (n + 1)th line is a blank space.
Output
For every test output one line giving the number of inversions of A.
Example
Input: 2 3 3 1 2 5 2 3 8 6 1 Output: 2 5
hide comments
liuxueyang:
20160717 15:16:16
@praval_singhal Thanks for your remind. I shouldn't use int for the ans. :(


davidgalehouse:
20160717 07:41:55
I don't know what BIT is and it seems too complicated. I did this with an ad hoc binary search tree. Add array values to BST with some bookkeeping. 

shubiks:
20160714 08:20:08
Great problem for learning application of Fenwick tree! :)


praval_singhal:
20160712 19:18:18
Got WA because of INT. 

puneethnaik:
20160712 09:18:03
good application of BIT 

ichfarbstift:
20160703 12:39:13
why is the problem tagged as shortest path? 

code0monkey1:
20160628 06:05:41
You would need to fully understand Merge sort/BIT to even start with this ... if you choose it to do via merge sort , this video will finally tell you the logic you need to use to count the number of inversions https://www.youtube.com/watch?v=hqeoAIryJOc 

get_right_jr:
20160626 20:07:32
Use long for number of inversions


baadshah_:
20160622 15:18:30
Don't use STL set (gives TLE) use MergeSort 

mkfeuhrer:
20160621 22:43:19
CLRS rocks :) AC in one go ! 
Added by:  Paranoid Android 
Date:  20100306 
Time limit:  3.599s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 