逆序对

定义

主要操作

时间及空间复杂度

时间复杂度

空间复杂度

模板

 1 #include<iostream>
 2 #include<cstdio>
 3 const int N=1000010;
 4 typedef long long int64;
 5 int64 data[N],merge[N];
 6 int64 tot,n;
 7 void MergeSort(int l,int r){
 8 	if(l==r) return;
 9 	int mid=(l+r)/2;
10 	MergeSort(l,mid);
11 	MergeSort(mid+1,r);
12 	int x=l,y=mid+1,k=l;
13 	while(x<=mid&&y<=r){
14 		if(data[x]<=data[y]){
15 			merge[k]=data[x];
16 			k++;x++;
17 		}else{
18 			merge[k]=data[y];
19 			k++;y++;
20 			tot+=mid-x+1;
21 		}
22 	}
23 	while(x<=mid){
24 		merge[k]=data[x];
25 		k++;x++;
26 	}
27 	while(y<=r){
28 		merge[k]=data[y];
29 		k++;y++;
30 	}
31 	for(int i=l;i<=r;i++) data[i]=merge[i];
32 }
33 int main(){
34 	scanf("%lld",&n);
35 	for(int i=1;i<=n;i++) scanf("%lld",&data[i]);
36 	MergeSort(1,n);
37 	printf("%lld",tot);
38 	return 0;
39 }