同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1113_逆序数

2022-5-16 18:16| 发布者: Hocassian| 查看: 68| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503611589400-Problem List-采集的数据-后羿采集器.html

Pro.ID

1113

Title

逆序数

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1113

AC

708

Submit

1305

Ratio

54.25%

时间&空间限制

Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

定义：在一个排列（ i₁, i₂, ..., i_t, ..., i_s, ..., i_n ）中，若数 i_t > i_s ，则称这两个数构成一个逆序。

定义：一个排列中所有逆序的总数称为此排列的逆序数。

现给出n个数的一个排列，求该排列的逆序数。

输入

多测试用例。第一行是一个正整数T，表示测试用例的个数。

每个测试用例占2行，第一行是该排列的整数的个数n （ 1 < n ≤ 50000 ），第二行是空格分隔的n个整数。

输出

Description

定义：在一个排列（ i₁, i₂, ..., i_t, ..., i_s, ..., i_n ）中，若数 i_t > i_s ，则称这两个数构成一个逆序。

定义：一个排列中所有逆序的总数称为此排列的逆序数。

现给出n个数的一个排列，求该排列的逆序数。

Input

多测试用例。第一行是一个正整数T，表示测试用例的个数。

每个测试用例占2行，第一行是该排列的整数的个数n （ 1 < n ≤ 50000 ），第二行是空格分隔的n个整数。

Output

为每个测试用例输出一行结果：该排列的逆序数。

Sample Input

2
5
3 2 5 1 4
10
-1 1 2 3 4 5 6 7 8 9

Sample Output

5
0

Hint

逆序数的求法至少有三种：枚举法、分治法、树状数组。本题时间放得比较宽，可以用枚举法去AC，但如果仅会用枚举法 ......

Author

John

样例输入