codechef Little Elephant and Permutations题解

the little elephant likes permutations. this time he has a permutation a[1], a[2], ..., a[n] of numbers 1, 2, ...,n.

he calls a permutation a good, if the number of its inversions is equal to the number of its local inversions. the number of inversions is equal to the number of pairs of integers (i; j) such that 1 ≤ i < j ≤ n and a[i] > a[j],

and the number of local inversions is the number of integers i such that 1 ≤ i < n and a[i] > a[i+1].

the little elephant has several such permutations. help him to find for each permutation whether it is good or not. print yes for a corresponding test case if it is good and no otherwise.

the first line of the input contains a single integer t, the number of test cases. t test cases follow. the first line of each test case contains a single integer n, the size of a permutation. the next line

contains n space separated integers a[1], a[2], ..., a[n].

for each test case output a single line containing the answer for the corresponding test case. it should beyes if the corresponding permutation is good and no otherwise.

1 ≤ t ≤ 474

1 ≤ n ≤ 100

it is guaranteed that the sequence a[1], a[2], ..., a[n] is a permutation of numbers 1, 2, ..., n.

总结一下有以下关系：

全局逆序数 == 起泡排序交换数据的交换次数

本题数据量小，可以使用暴力法计算。

但是这样时间效率是o(n*n)，要想降低到o(nlgn)那么就要使用merger sort。

下面一个类中暴力法和merge sort方法都包括了。