洛谷 P1908 逆序对

题目链接：

https://www.luogu.com.cn/problem/P1908

题目大意：

给长为 n 的序列，求序列中逆序对的数目

思路：

一、
归并：

#include 
using namespace std;
#define LL long long
const int N = 5e5 + 10;
LL a[N], tmp[N], n, ans = 0;
void mergeSort(LL l, LL r){
	if (l >= r) return;
	LL mid = (l + r) >> 1, i = l, j = mid + 1, cnt = 0;
	mergeSort(l, mid);
	mergeSort(mid + 1, r);
	while (i <= mid || j <= r)
		if (j > r || (i <= mid && a[i] <= a[j]))
			tmp[cnt++] = a[i++];
		else
			tmp[cnt++] = a[j++], ans += mid - i + 1;
	for (LL k = 0; k < r - l + 1; k++)
		a[l + k] = tmp[k];
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	mergeSort(1, n);
	cout << ans << "\n";
	return 0;
}

二、
树状数组：

#include 
using namespace std;
#define LL long long
const int N = 5e5 + 10;
LL ans;
int n, tree[N], p[N];
struct node{
	int num, index;
}nd[N];
bool cmp(node a, node b){
	if (a.num == b.num) return a.index < b.index;
	return a.num < b.num;
}
int lowbit(int k){
	return k & -k;
}
void update(int x, int k){
	while (x <= n){
		tree[x] += k;
		x += lowbit(x);
	}
}
int query(int x){
	int t = 0;
	while (x != 0){
		t += tree[x];
		x -= lowbit(x);
	}
	return t;
}
void solve(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		scanf("%d", &nd[i].num);
		nd[i].index = i;
	}
	sort(nd + 1, nd + n + 1, cmp);
	for (int i = 1; i <= n; i++)
		p[nd[i].index] = i;
	for (int i = 1; i <= n; i++){
		update(p[i], 1);
		ans += (i - query(p[i]));
	}
	cout << ans << "\n";
}
int main(){
	solve();
	return 0;
}