P1908 逆序对

//本题用归并排序来写，大概是用O(n log n)的时间复杂度 
#include <iostream>

using namespace std;

const int N = 5e5 + 5;

long long n,a[N],b[N],ans;//a[i]存要排序的数组，b[i]作为中转，把已经排好序了的值再赋给a[i]，ans存答案 
//记得开 long long ans会爆int 
void merge (int l,int r) {//归并排序板子 
	
	if ((r - l) == 0) return ;//如果说这个区间的长度为1了就不需要继续往下分了，返回上一层 
	
	int mid = (l + r) / 2;//二分，以mid作为边界值 
	int i = l,j = mid + 1,cnt = l;//i为了不影响l值的变化而新开的一个变量，j取第二个区间的边界值，cnt存排序的长度 
	
	merge (l,mid);//让第一个区间进行二分，使得它变有序 
	merge (mid + 1,r);//同第一个一样 
	
	while (i <= mid && j <= r) {//遍历完这两个区间共同有的长度 
		
		if (a[i] <= a[j]) {//如果说第一个区间的最小值小于第二个区间的最小值，就把它加进b数组 
			b[cnt ++] = a[i];//加入数组 
			i ++;//跳到第一个序列的第二个元素 
		} else {//所以答案就加第一个区间的长度 
			ans += mid - i + 1;//因为如果他比第一个区间的最小值要小的话，那么说明第一个区间的所有数都比他大，又因为第一个区间的数都在他前面，所以都构成逆序对 
			b[cnt ++] = a[j];//同上 
			j ++;//更新元素 
		}
	}
	
	for (i ;i <= mid;i ++) b[cnt ++] = a[i];//如果说第一个区间还剩余元素没加，直接全加进去 
	for (j ;j <= r; j ++) b[cnt ++] = a[j];//同上 
	for (int k = l;k <= r;k ++) a[k] = b[k];//最后再赋给a数组已经排好序了的值 
	
}

int main () {
	
	cin >> n;
	
	for (int i = 1;i <= n;i ++) cin >> a[i];
	
	merge (1,n);//归并排序 
	
//	for (int i = 1;i <= n;i ++) {
//		cout << b[i] << '\n';
//	}
	
	cout << ans << '\n';//输出答案 
	return 0;//华丽结束 
}