Sort

time limit per test 2 second memory limit per test 256 megabytes
You want to process a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order.

传送门:EOJ3234

Input

There are several test cases, please process till EOF.
For each test case, the first line contains integer n (1≤n≤10^5). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤10^9).

Output

For each test case, output the minimum times of swapping in one line.

Sample Input

1
2
2
1 2

Sample Output

1
0

题解

典型求逆序对问题
此处要注意当数组元素个数很大时,逆序对的数量会很大,此时需要long来存储

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.io.*;  
import java.util.*;
public class Main {
static long count;
static int[]temp;
static int[]shu;
public static void main(String[] args) {
FastScanner sc = new FastScanner();
PrintWriter pw = new PrintWriter(System.out);
//int t=sc.nextInt();
int k=0;
while (sc.hasNext()) {
k++;
int n=sc.nextInt();
shu=new int[n];
temp=new int[n];
count=0;
for(int i=0;i<n;i++)shu[i]=sc.nextInt();
mergeSort(shu,0,n-1);
//pw.printf("Scenario #"+k+":\n");
pw.printf("%d\n",count);
pw.flush();
}
}
static void mergeSort(int[]shu,int left,int right){
if(left<right){
int mid=(left+right)/2;
mergeSort(shu,left,mid);
mergeSort(shu,mid+1,right);
merge(shu,left,mid,right);
}
}
/*static void merge(int[]input,int left,int center,int right){
int []tempArray = new int[right-left+1];
int mid = center+1;
int temp = left;
int current = 0;
while(left<=center && mid<=right){
if(input[left]>input[mid]){
tempArray[current++]=input[mid++];
count+=center-left+1;
}else{
tempArray[current++]=input[left++];
}
}
while(left<=center){
tempArray[current++]=input[left++];
}
while(mid<=right){
tempArray[current++]=input[mid++];
}
current=0;
while(temp<=right){
input[temp++]=tempArray[current++];
}
}
*/static void merge(int[]shu,int left,int mid,int right){
int k=left;
int a=left;
int b=mid+1;
while(a<=mid&&b<=right){
if(shu[a]>shu[b]){
temp[k++]=shu[b++];
count+=mid-a+1;
}else{
temp[k++]=shu[a++];
}
}
while(a<=mid){
temp[k++]=shu[a++];
}
while(b<=right){
temp[k++]=shu[b++];
}
for(int i=left;i<=right;i++){
shu[i]=temp[i];
}
}
/*static void merge(int[]shu,int l,int m,int r)
{
int i = l;
int j = m + 1;
int k = l;
while(i <= m && j <= r)
{
if(shu[i] > shu[j])
{
temp[k++] = shu[j++];
count += m - i + 1;
}
else
{
temp[k++] = shu[i++];
}
}
while(i <= m) temp[k++] = shu[i++];
while(j <= r) temp[k++] = shu[j++];
for(int q=l;q<=r;q++)
shu[q] = temp[q];
}*/
}