SPOJ INVCNT

题目链接：http://www.spoj.com/problems/INVCNT/

题目大意：求数组中逆序数的个数。即满足 i < j, a[i] > a[j] 的数的个数。

解题思路：可以使用归并排序求逆序数，每次归并的时候记录一下：

假如归并 va = {3 5 6} 和 vb = {1 2 3}，那么对于3来说，逆序数有2个；对于5，6来说有3个。简单记录一下即可。

也可以使用树状数组，枚举每个数字查询比他大的数字出现了几个。不过当数组元素过大的时候需要离散化。

代码：

 1 const int maxn = 1e6 + 5;
 2 int n;
 3 int a[maxn];
 4 ll ans = 0;
 5 
 6 VI mymerge(VI va, VI vb){
 7     VI vc;
 8     int i = 0, j = 0;
 9     while(i < va.size() || j < vb.size()){
10         while((i >= va.size() && j < vb.size()) || (j < vb.size() && va[i] > vb[j])){
11             vc.push_back(vb[j++]);
12         }
13         if(i < va.size()) {
14             vc.push_back(va[i++]);
15             ans += j;
16         }
17     }
18     return vc;
19 }
20 VI mergesort(VI va){
21     int t = va.size();
22     if(t > 1){
23         VI vb, vc;
24         for(int i = 0; i < t / 2; i++) vb.push_back(va[i]);
25         for(int i = t / 2; i < va.size(); i++) vc.push_back(va[i]);
26         vb = mergesort(vb); 
27         vc = mergesort(vc);
28         va = mymerge(vb, vc);
29     }
30     return va;
31 }
32 void solve(){
33     ans = 0;
34     VI va;
35     for(int i = 0; i < n; i++) va.push_back(a[i]);
36     mergesort(va);
37     printf("%lld
", ans);
38     va.clear();
39 }
40 int main(){
41     int t;
42     scanf("%d", &t);
43     while(t--){
44         scanf("%d", &n);
45         for(int i = 0; i < n; i++) scanf("%d", &a[i]);
46         solve();
47     }
48 }

题目：

INVCNT - Inversion Count

#graph-theory #number-theory #shortest-path #sorting #bitmasks

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