14099 - 求逆序对

给定一个长度为 n 的整数序列 a_1, a_2, \dots, a_n 。若存在下标 i < j 且 a_i > a_j ，则称数对 (i, j) ) 为一个逆序对。

请你计算该序列中逆序对的总数。

• 第一行包含一个整数 n（ 1 \le n \le 5 \times 10^5 ），表示序列的长度。
• 接下来 n 行，每行一个整数 a_i ，表示序列中的第 i 个数（ |a_i| \le 10^9 ）。

输出一个整数，表示逆序对的总数。答案可能很大，请使用 64 位整数（long long）存储。

样例说明

序列为 3, 2, 3, 2，逆序对有：

• (1, 2)：3 > 2
• (1, 4)：3 > 2
• (3, 4)：3 > 2

共 3 个。

数据范围与约定

• 1 \le n \le 5 \times 10^5
• |a_i| \le 10^9

一本通