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
|
lakshay_v06:
2016-01-28 13:01:16
If this is the first question you are trying to do using BIT, then please try some other questions of BIT before this one.... It took me quite some while to figure out the logic behind this question's BIT implementation.... :) |
|
ibrahim5253:
2016-01-24 20:49:14
Thanks @Kartik. I would have toiled for hours to figure out the WA. |
|
amit013:
2016-01-21 19:52:28
nice problem !!!
|
|
Papai:
2016-01-11 00:41:57
Last edit: 2016-01-11 00:52:52 |
|
manas0008:
2016-01-05 19:46:17
use long long int(better...for all variables)....and better...try using merge sort algorithm! |
|
darkhire21:
2016-01-05 14:59:16
2nd test-case n= 5-> 2 3 8 6 1
|
|
abhigupta4:
2015-12-29 18:04:11
For all those struggling to understand how exactly merge sort will be useful should refer this
|
|
Kartik:
2015-12-26 06:55:33
keep n long long, cost me a WA |
|
Shubham Gupta:
2015-12-18 21:20:46
Only keep the counter as long long.
|
|
archit saxena:
2015-12-17 17:48:21
omg took 10 hours to solve use mergesort to get O(nlogn)time.bubblesort might look attractive at first but gives O(n^2)time
|
| 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 |
RSS