P1908 逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又开始较量了。作为成年人,他们已经不满足于你追我赶的游戏,转而喜欢上了统计。
TOM 查阅到一个被人类称作逆序对的东西:给定一个正整数序列,若存在两个下标 i,j 满足 i<j 且 ai>aj,则称下标 i 与 j 构成一个逆序对。
现在给定一个长度为 n 的正整数序列 {a1,a2,…,an},请你帮他们算出序列中逆序对的数量。注意序列中可能有重复数字。
输入格式
第一行输入一个整数 n(1≦n≦5×105) 代表序列中的元素数量。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表给定的序列。
输出格式
在一行上输出一个整数,代表序列中逆序对的数量。
测试样例
6
5 4 2 6 3 1
11
样例 1 解释
序列为 {5,4,2,6,3,1},按较大的那个元素分类统计逆序对:
∙以 a1=5 为较大元素,它与 a2=4、a3=2、a5=3、a6=1 分别构成逆序对,共 4 个;
∙以 a2=4 为较大元素,它与 a3=2、a5=3、a6=1 分别构成逆序对,共 3 个;
∙以 a3=2 为较大元素,它与 a6=1 构成逆序对,共 1 个;
∙以 a4=6 为较大元素,它与 a5=3、a6=1 分别构成逆序对,共 2 个;
∙以 a5=3 为较大元素,它与 a6=1 构成逆序对,共 1 个。
因此答案为 4+3+1+2+1=11。
7
6 6 2 9 3 1 5
13
提示
对于 25% 的数据,1≦n≦2.5×103;
对于 50% 的数据,1≦n≦4×104;
对于所有数据,1≦n≦5×105,1≦ai≦109。