2935. 逆序对的数量
时间限制：1000 MS 内存限制：128 MB
题目描述
# 逆序对的数量 ## 题目描述 给定一个长度为 $n$ 的整数数列，请计算数列中逆序对的数量。 对于数列中的两个元素 $a[i]$ 和 $a[j]$，如果满足 $i < j$ 且 $a[i] > a[j]$，则称 $(i,j)$ 为一个逆序对。 请输出逆序对的总数量。相等的元素不构成逆序对。 ## 输入格式 输入文件名为 `reverses.in`。 第一行包含一个整数 $n$，表示数列的长度。 第二行包含 $n$ 个整数 $a[i]$，表示数列中的元素。 ## 输出格式 输出文件名为 `reverses.out`。 输出一个整数，表示满足 $i < j$ 且 $a[i] > a[j]$ 的数对数量。 ## 数据范围 对于所有数据： - $1 \le n \le 100000$； - $1 \le a[i] \le 10^9$； - 答案范围为 $0$ 至 $\frac{n(n-1)}{2}$，最大为 $4999950000$，请使用 64 位整数存储答案。 ## 样例输入 ``` 6 2 3 4 5 6 1 ``` ## 样例输出 ``` 5 ```