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
satyajit tourani:
2015-06-11 08:18:34
easy after reading theory from CLRS( mergesort ) :) AC in 0.27 seconds. :D |
|
Akash Goel:
2015-06-10 21:13:39
Couldn't AC without long long. Dunno why |
|
Nitesh Tiwari:
2015-06-05 11:14:02
Reading these comments does help a lot.
|
|
Praveen Kulkarni:
2015-06-03 15:59:39
my 50th |
|
hrwang_xn:
2015-06-01 17:37:57
use BIT. |
|
scyth3r:
2015-05-27 14:21:16
@I W G T J have you considered blank lines as input? |
|
I W G T J:
2015-05-27 09:59:18
Why WA? <snip>
|
|
scyth3r:
2015-05-26 19:42:48
tough for python....challenge for pythonistas
|
|
i_am_looser:
2015-05-18 14:48:01
Done it using segment tree.... |
|
:.Mohib.::
2015-05-17 08:08:19
Binary tree ==> AC :) |
Added by: | Paranoid Android |
Date: | 2010-03-06 |
Time limit: | 3.599s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: PERL6 |