逆数对（树状数组的方法）

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

输入
`5 4 5 1 3 2`

输出
7

思路：

根据题意，求逆序对总数。

逆序对含义：如果数组中的两个不同位置，前面的数字比后面的数字严格大，则称其为一个逆序对。

根据样例已知： 4 5 1 3 2

我们可以通过计数的方式，log(n)的时间复杂度获取逆序对。

方式如下：

每输入一个 x 后

0	0	0	0	0
1	2	...	4	5

就开始询问有多少个逆序对，求总和（x + 1 ~ INF）的数量是多少。

比如当输入到 1 的时候：

1	0	0	1	1
1	2	3	4	5

逆序对的数量为： sum(2 ~ INF) = 0 + 0 + 1 + 1 + 0 + ... + 0 = 2

依此类推。

这里利用到了树状数组（单点添加，区间查询）。操作函数看我以往的笔记。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();

signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
	// cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int R = 100010;	// 题目 a[i] 的临界范围
int cnt[N];	// 用于计数
inline int lowbit(int x){return x&(-x);}
// 单点添加函数
inline void Add_pos(int pos,int x)
{
	for(int i = pos;i <= R;i += lowbit(i)) cnt[i] += x; 
}
// 区间询问函数	变相的获取逆序对
inline int ask(int l,int r)
{
	int ans = 0;
	for(int i = l - 1;i;i-=lowbit(i)) ans -= cnt[i];
	for(int i = r;i;i-=lowbit(i)) ans += cnt[i];
	return ans;
}
inline void solve()
{
	int n,x,ans = 0;
	cin >> n;
	while(n--)
	{
		cin >> x;
		Add_pos(x,1); // 单点添加，统计
		ans += ask(x + 1,R);	// 询问总和，获取逆序对数量
	}
	cout << ans << endl;
}