---

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

原创 已于 2024-04-23 20:53:42 修改 · 粉丝可见 · 579 阅读 · 5 · 6 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/138137595

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

题目：

样例：

cpp<br/>5<br/>4 5 1 3 2<br/>

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;
}

最后提交：