A7962.逆序对

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小码君和小码酱最近又较量上了,但他们现在是大孩子了,不喜欢再玩小游戏,现在他们喜欢玩统计。

最近,小码君了解到一个称之为“逆序对”的东西,逆序对是指:对于给定的一段正整数序列,逆序对就是序列中 ai>aja_i>a_ji<ji<j 的有序对。

比如序列{3,2,1}中,{3,2}、{3,1}、{2、1}都为逆序对。

知道逆序对的概念后,给定一个正整数序列,小码君和小码酱比赛谁先算出序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行,一个数 nn,表示序列中有 nn个数。

第二行 nn 个数,表示给定的序列。序列中每个数字不超过 10910^9

输出格式

输出序列中逆序对的数目。

输入输出样例

  • 输入#1

    6
    5 4 2 6 3 1

    输出#1

    11

说明/提示

0<n0<n \le 5×1055 \times 10^5

【普及组算法3】排序

0/8
首页