2402. 逆序对
1000ms
256MB
简单
树状数组
线段树
题目描述
对于一个长度为 $n$ 的整数序列 $a$，如果存在一组下标 $(i,j)$ 满足：
- $i < j$
- $a_i > a_j$
那么称 $(i,j)$ 为该序列中的一个**逆序对**。
现在给定一个整数序列，请你统计其中逆序对的总数量。
输入格式
- 第一行输入一个整数 $n$，表示序列长度。
- 第二行输入 $n$ 个整数，表示序列中的元素。
输出格式
- 输出一个整数，表示序列中的逆序对数量。
样例 1
输入 (Input)
输出 (Output)
样例说明
序列：
```
5 4 2 6 3 1
```
其中逆序对包括：
```
(5,4)
(5,2)
(5,3)
(5,1)
(4,2)
(4,3)
(4,1)
(2,1)
(6,3)
(6,1)
(3,1)
```
共计 $11$ 个。
- 对于 $25\%$ 的数据：$n \le 2500$
- 对于 $50\%$ 的数据：$n \le 4 \times 10^4$
- 对于 $100\%$ 的数据：
- $1 \le n \le 5 \times 10^5$
- $0 \le a_i \le 10^9$
由于数据规模较大，不能使用 $O(n^2)$ 的双重循环暴力统计。
本题推荐使用：
- **归并排序统计逆序对**
- 或 **树状数组 + 离散化**
其中归并排序做法的核心思想为：
1. 将数组递归划分为左右两部分。
2. 左右部分分别统计逆序对数量。
3. 在归并两个有序区间时：
- 若左侧元素大于右侧元素，
- 则左侧当前元素及其后面的所有元素都与右侧元素形成逆序对。
4. 在归并过程中即可完成统计。
整体时间复杂度为：
$$
O(n \log n)
$$
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功