NC15163 逆序数 归并

给定一个数组,求逆序对个数

• 逆序对个数等于冒泡排序的交换次数
• 归并排序的过程中可以统计出答案
• 不开 $longlong$long long凉凉
  

void merge_sort(int lef, int rig) {
	if(lef == rig) return ;
	int mid = (lef + rig) >> 1;
	merge_sort(lef, mid);
	merge_sort(mid+1, rig);
	int x = lef, y = mid + 1, i = 0;
	for( ; i<(rig-lef+1); i++) {
		if(x<=mid && y<=rig) { //发生逆序
			if(a[x] > a[y]) {
				ans += mid - x + 1; //统计答案
				tmp[i] = a[y++];
			} else
				tmp[i] = a[x++];
		} else {
			if(x <= mid) tmp[i] = a[x++];
			if(y <= rig) tmp[i] = a[y++];
		}
	}
	while(~(--i)) a[rig--] = tmp[i];
}

完整代码

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif


int n, m, Q, K, a[MAXN], tmp[MAXN];
ll ans;

void merge_sort(int lef, int rig) {
// forarr(a, lef, rig);
	if(lef == rig) return ;
	int mid = (lef + rig) >> 1;
	merge_sort(lef, mid);
	merge_sort(mid+1, rig);
	int x = lef, y = mid + 1, i = 0;
	for( ; i<(rig-lef+1); i++) {
		if(x<=mid && y<=rig) {
			if(a[x] > a[y]) {
				ans += mid - x + 1;
				tmp[i] = a[y++];
			} else
				tmp[i] = a[x++];
		} else {
			if(x <= mid) tmp[i] = a[x++];
			if(y <= rig) tmp[i] = a[y++];
		}
	}
	while(~(--i)) a[rig--] = tmp[i];
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n);
	for(int i=1; i<=n; i++) read(a[i]);
	merge_sort(1, n);
// forarr(a, 1, n);
// show(ans);
	printf("%lld\n", ans);



#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}