求逆序对个数

题目描述:

 

正因为某些算法的特殊性，会使其在解决问题的同时连带产生了副产品。但在不同的需求下，副产品也会变成题目的解。 

输入一个长度为n的序列，求序列中逆序对的个数。逆序对即 Ai>Aj（i<j）

 

输入格式:

第一行：一个数n 
接下来n行，每行一个数Ai

输出格式:

一个数，即这个序列的逆序对个数

样例输入:

5
4
2
1
3
5

样例输出:

4

提示:

对于100%的数据:n<=150,000;0<=Ai<=100,000,000

时间限制: 1000ms
空间限制: 128MB

---

来源: 原创