SPOJ.com - Problem INVCNT

INVCNT - Inversion Count

#number-theory #sorting

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	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 https://youtu.be/B29dVmpIpn0 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.
	sangmai: 2020-01-17 03:14:50 AC in one go using merge sort
	sajalagrawal14: 2019-12-03 13:46:03 Can be solved Using 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
	codefresher: 2019-11-22 22:44:54 Good one....solved using merge sort tree...segment tree???

Submit solution!

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