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.


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.


For every test output one line giving the number of inversions of A.






hide comments
dardev: 2020-07-03 16:48:44

The concept is covered very well here ->

mukul202: 2020-05-19 17:39:01

Just solved this question using:
1)merge sort
2)fenwick tree
3)segment tree
Now trying with tries:)

picchi_67: 2020-05-06 05:46:10

Can be Solved Easily with merge sort.
Great problem for BIT Practice....Use " Long Long Int ".
Hint: use element value.

mt6170078: 2020-04-21 16:14:30

why tag of Bitmask? how to use Bitmask here??

yourmom__: 2020-04-21 07:40:01

I see the question. Okay. Thought of a simple O(n^2) algo. Then I submit and get TLE. Offcourse. Then I see the commenst section. People are commenting about Fenwick trees? Segment trees? Self balancing BST? Now WHAT THE FUCK are these? Spent 2-3 days learning their basics. People who are getting TLE, spend sometime learning these new data structures, ans dont give up.
Happy Coding bois

edit: The answer can be >2^32, so use long. Things like this should be mentioned in the statment. I wasted 30 mins just because of this

Last edit: 2020-04-21 10:15:37
offamitkumar: 2020-03-29 10:47:02

Solved it With
1)Segment tree
2)fenwick tree (with or without cordinate compression)
3)merge sort
4)policy based data structure in c++ (vary small code, even smaller than fenwick tree)
5)Self Balancing Bst
6) Trie Data Structure (This one is interesting)

Last edit: 2020-03-29 10:47:44
vishesh_2308: 2020-03-12 10:57:36
Check this video if you are not able to understand the merge sort algo

terminator_pk: 2020-02-07 19:18:21

Last edit: 2020-02-08 12:55:30
savage_19: 2020-02-04 08:30:10

1. Do it with merge sort first.
2. Then try it with Fenwick or Binary indexed tree.
3. After that, if you want you can solve it using,
* AVL tree (Self-balancing BST)
* Segment tree
4. By trying out these things, you will get used to those data structures and algorithms.
5. Also use long data type in java and long long in c++ to count the number of inversions.

Last edit: 2020-02-04 08:32:27
avsd_47: 2020-01-21 18:22:23

Caution:the answer you are going to print must be of type long long costed me 3 wa's.

Added by:Paranoid Android
Time limit:3.599s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6