I. 逆序对

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小L最近在复习逆序对的概念，需要统计一个序列中逆序对的数量。逆序对的定义是：对于序列中两个元素 $a_i$ 和 $a_j$ ,如果 $i \lt j$ 且 $a_i \gt a_j$ 则 $(i, j)$ 构成一个逆序对。两个逆序对只要下标不同（即 $i_1 \neq i_2$ 或 $j_1 \neq j_2$ ），就视为不同的逆序对。

输入格式

第一行输入一个整数 $n\ (2 \leq n \leq 10^6)$ ，表示序列的长度。

第二行输入 $n$ 个整数，第 $i$ 个数表示 $a_i\ (1 \leq a_i \leq 30)$ 。

输出格式

输出序列中逆序对的总数量。

输入输出样例 #1

输入 #1

4
3 3 2 1

输出 #1

说明/提示

该序列中的逆序对为：

$(1, 3)$ 、 $(1, 4)$ 、 $(2, 3)$ 、 $(2, 4)$ 、 $(3, 4)$ ，共 $5$ 个。

西华师范大学数学科学学院第十届高级程序语言设计大赛（同步赛）

未参加

状态: 已结束
规则: XCPC
题目: 14
开始于: 2025-11-30 13:00
结束于: 2025-12-13 13:00
持续时间: 312 小时
主持人: admin
参赛人数: 37

I. 逆序对

逆序对

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

西华师范大学数学科学学院第十届高级程序语言设计大赛（同步赛）

状态

开发

支持

关于

I. 逆序对

逆序对

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

西华师范大学数学科学学院第十届高级程序语言设计大赛（同步赛）

状态

开发

支持

关于

还没有账户？

登录