Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
||||||||||||||
2019-11-22 21:51:35
my first fenwick tree question :) |
||||||||||||||
2019-11-10 05:27:54
Used BIT and inversions count to solve the problem. |
||||||||||||||
2019-11-05 10:36:43
we can use ordered set (pb_ds) to solve this.... |
||||||||||||||
2019-11-03 10:56:10
Solve using Merge sort first, after that solve it with BIT (Binary indexed tree). AC in one go ;) |
||||||||||||||
2019-11-01 04:44:13
input explanation is garbage , but BIT DESTROY it!! |
||||||||||||||
2019-09-13 11:13:23
AC in 3 GO because of long long! |
||||||||||||||
2019-09-09 08:32:00
can anyone please tell me how to solve it using segment tree....? please knock at noonehere@gmail.com Last edit: 2022-06-26 16:01:13 |
||||||||||||||
2019-08-30 13:46:30
what rubbish and confusing input method. |
||||||||||||||
2019-08-15 12:14:19
solved it using PBDS |
||||||||||||||
2019-07-09 00:47:06
AC in one go using merge sort, very nice problem |