树状数组求逆序对

分析

用 $\text{map}$ 对数组离散化，防止撑爆树状数组。

从左到右扫一遍数组。$i-1$ 表示左边有 $i$ 个数。显然左边的数与 $a_i$ 构成逆序对的数量为 $i-1$ 减左边比 $a_i$ 小的数的数量。

记得去重。

code

#include <bits/stdc++.h>
#define rei register int
#define N 1000010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

ll n, a[N], tot, b[N], ans, tr[N];
map<ll, ll> id;

inline ll lowbit(ll x) {return x & -x;}
inline void add(ll x) {while (x <= n) tr[x]++, x += lowbit(x);}
inline ll query(ll x) {ll ret = 0; while (x) ret += tr[x], x -= lowbit(x); return ret;}

int main()
{
	read(n);
	for (rei i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n); tot = unique(b + 1, b + 1 + n) - b - 1; 
	for (rei i = 1; i <= tot; i++) id[b[i]] = i;
	for (rei i = 1; i <= n; i++)
	{
		ans += i - query(id[a[i]]) - 1;
		add(id[a[i]]);
	}
	printf("%lld", ans);
	return 0;
}