1382: 逆序对

内存限制:128 MB 时间限制:2.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:137 通过:42

题目描述

对于一个包含N个非负整数的数组A[1..n],如果有i < j,且A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对。   例如,数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2),共4个。 

求n个数中的逆序对个数。

输入格式

第一行一个整数n(<=1,000,000) 
第二行n个整数,a[i]<=2^31-1 

输出格式

n个数中逆序对个数

输入样例 复制

5
3 1 4 5 2

输出样例 复制

4

分类标签