#B. 逆序对的数量

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $N$ 的序列 $A$ ，如果对于下标 $i < j$ 且 $A[i] > A[j]$ ，那么我们称 $(i, j)$ 为一个逆序对。请求出序列中逆序对的总数。

第一行 $N$ ( $1 \le N \le 5 \times 10^5$ )。第二行 $N$ 个整数。

一行一个整数，表示逆序对个数。

6
5 4 2 6 3 1

序列为 $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个