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
affan12347:
2021-01-15 16:03:56
monka s . naive array approach doesnt work , gives tle Last edit: 2021-01-15 16:04:21 |
|
tejasreddyk:
2021-01-14 16:29:27
monkagiga count normal variable and std::count messed me up |
|
sudo_s:
2021-01-01 15:07:07
Very Weak test Cases.
|
|
anurag_mishra:
2020-11-28 14:06:41
Take array size 10^7+1 to remove SIGSEGV error |
|
samartha_5611:
2020-08-20 12:56:34
make bit array of size 2e5+5, otherwise Segmentation falut will come
|
|
coolboy7:
2020-07-30 15:26:02
answer will be in range of long long |
|
robosapien:
2020-07-21 18:11:41
use long long. |
|
dardev:
2020-07-03 16:48:44
The concept is covered very well here -> https://www.youtube.com/watch?v=7_AJfusC6UQ |
|
mukul202:
2020-05-19 17:39:01
Just solved this question using:
|
|
picchi_67:
2020-05-06 05:46:10
Can be Solved Easily with merge sort.
|
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 |