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 23 24 25 26 27 28 29 30 31 32 33 Next >

	Mr Tambourine Man: 2014-05-10 13:36:33 use long long int..that cost me two WA
	californiagurl: 2014-03-03 09:18:07 didn't do anything special for duplicates.....but got AC in 2 sec :) but i'd still like to know how can i improve on the time limit,,, lot many users got it done within 1 sec. Last edit: 2014-03-03 09:24:44
	Ajay Prasadh: 2014-02-20 13:12:06 Check for duplicate numbers finally ac ! :D
	Anubhav Balodhi : 2014-02-04 07:52:44 good Inversion problem... AC :-D
	rahul kumar: 2013-12-24 09:40:32 did it using merge sort...easy one
	Achmet ibn Rashid: 2013-12-12 16:51:56 Tried both merge sort and binary indexed (aka fenwick) trees; got AC with both well within bounds, but merge sort was a lot faster: * NlogN < NlogVmax -- Nmax is 2 * 10^5, Vmax is 10^7 * you can use the actual N, you don't need to use Nmax, but you need to use Vmax in the BIT for insertion if you don't read the whole vector first. * merge sort should be more cache friendly. * resetting the BIT is O(V); even with memset I suspect that also eats a lot of time, even when clearing only the dirty region. Edit: there are no duplicate numbers btw; the problem statement says so and my BIT solution wouldn't have worked if there were. Last edit: 2013-12-12 16:53:51
	Achmet ibn Rashid: 2013-12-12 16:02:28 Last edit: 2013-12-12 16:56:11
	Bo MA: 2013-10-17 06:30:56 Take care about two things: 1. The output would exceed INT_MAX, use long long instead 2. Duplicate numbers
	P_Quantum: 2013-08-28 09:17:26 Finally accepted..!! Silly mistake costed me many WA..
	Geanyous: 2013-07-10 05:01:21 lol printing "%d" instead of "%lld" cost me an WA..

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