LG#P1908. 逆序对

逆序对

P1908 逆序对

题目描述

\hspace{15pt}猫猫 TOM 和小老鼠 JERRY 最近又开始较量了。作为成年人,他们已经不满足于你追我赶的游戏,转而喜欢上了统计。

\hspace{15pt}TOM 查阅到一个被人类称作逆序对的东西:给定一个正整数序列,若存在两个下标 i,ji, j 满足 i<ji<j 且 ai>aja_i>a_j,则称下标 ii 与 jj 构成一个逆序对。

\hspace{15pt}现在给定一个长度为 nn 的正整数序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},请你帮他们算出序列中逆序对的数量。注意序列中可能有重复数字。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦5×105)n \left(1 \leqq n \leqq 5 \times 10^5\right) 代表序列中的元素数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表给定的序列。

输出格式

\hspace{15pt}在一行上输出一个整数,代表序列中逆序对的数量。

测试样例

6
5 4 2 6 3 1
11

样例 1 解释

\hspace{15pt}序列为 {5,4,2,6,3,1}\{5, 4, 2, 6, 3, 1\},按较大的那个元素分类统计逆序对:

∙ \hspace{23pt}\bullet\,以 a1=5a_1=5 为较大元素,它与 a2=4a_2=4、a3=2a_3=2、a5=3a_5=3、a6=1a_6=1 分别构成逆序对,共 44 个;

∙ \hspace{23pt}\bullet\,以 a2=4a_2=4 为较大元素,它与 a3=2a_3=2、a5=3a_5=3、a6=1a_6=1 分别构成逆序对,共 33 个;

∙ \hspace{23pt}\bullet\,以 a3=2a_3=2 为较大元素,它与 a6=1a_6=1 构成逆序对,共 11 个;

∙ \hspace{23pt}\bullet\,以 a4=6a_4=6 为较大元素,它与 a5=3a_5=3、a6=1a_6=1 分别构成逆序对,共 22 个;

∙ \hspace{23pt}\bullet\,以 a5=3a_5=3 为较大元素,它与 a6=1a_6=1 构成逆序对,共 11 个。

\hspace{15pt}因此答案为 4+3+1+2+1=114+3+1+2+1=11。

7
6 6 2 9 3 1 5
13

提示

\hspace{15pt}对于 25%25\% 的数据,1≦n≦2.5×1031 \leqq n \leqq 2.5 \times 10^3;

\hspace{15pt}对于 50%50\% 的数据,1≦n≦4×1041 \leqq n \leqq 4 \times 10^4;

\hspace{15pt}对于所有数据,1≦n≦5×1051 \leqq n \leqq 5 \times 10^5,1≦ai≦1091 \leqq a_i \leqq 10^9。