跳至正文
题库3986
#3986

1311. 【例2.5】求逆序对

查看题目操作

1311. 【例2.5】求逆序对

题目描述

给定一个序列a1,a2,…,ana_1,a_2,…,a_n,如果存在 1≤i<j≤n1\le i\lt j\le n 且 ai>aja_i>a_j,那么我们称之为逆序对,求逆序对的数目。

输入格式

第一行为nn,表示序列长度,接下来的nn行,第i+1i+1行表示序列中的第ii个数。

输出格式

所有逆序对总数。

4
3
2
3
2
3

提示

1≤N≤105,1≤Ai≤1051≤N≤10^5,1≤A_i≤10^5;逆序对总数可能超过 32 位整数。

来源

一本通在线评测 ybtbas-1311