프로그램 명: ncpc_mega
제한시간: 1 초
[문제 요약]
O(n^2)의 시간복잡도를 갖는 정렬 알고리즘은 매우 단순합니다. 서로 이상한 위치에 있는 두 원소를 선택한 뒤 이를 교환하면 됩니다. (보충:오름차순 정렬의 경우 앞의 원소가 뒤의 원소보다 큰 경우 이상한 것이므로 이 둘을 교환합니다.)
Conrad는 2개의 원소를 선택하는 것이 아닌 3개를 선택하는 알고리즘을 생각했습니다. 그것은, 3개의 원소 a_i > a_j > a_k (단 i < j< k) 를 선택하고 이를 a_k, a_j, a_i 순으로 재배열하는 것입니다.
원래의 정렬 알고리즘은 최대 원소 교환 횟수가 n(n-1)/2번입니다. Conrad는 수열이 주어졌을 때 위의 알고리즘으로 최대 몇 번을 교환해야 하는지를 알고자 합니다. 그는 어떠한 수열이 주어졌을 때 위 조건을 만족하는 순서쌍 (i,j,k) 의 갯수를 구하는 프로그램을 작성해 달라고 당신에게 요청했습니다.
입력
-
첫째 줄에 수열의 길이 n (1<=n<=10^5)가 주어집니다.
-
둘째 줄에 정수 수열 a1, a2, a3, ..., an이 공백을 구분으로 하여 주어집니다. 이 때 각 원소들의 범위는 1 이상 n 이하임이 보장됩니다.
출력
a_i > a_j > a_k, i < j < k의 조건을 모두 만족하는 순서쌍 (i,j,k) 의 갯수를 출력합니다.
The n^2 upper bound for any sorting algorithm is easy to obtain: just take two elements
that are misplaced with respect to each other and swap them. Conrad conceived an algorithm
that proceeds by taking not two, but three misplaced elements. That is, take three elements
ai > aj > ak with i < j < k and place them in order ak, aj , ai. Now if for the original algorithm
the steps are bounded by the maximum number
of inversions n(n-1)/2 , Conrad is at his wits' end as to the upper bound for such triples in a given sequence. He asks you to write a program
that counts the number of such triples.
입력
The First line of the input is the length of the sequence, 1 <= n <= 10^5.
The next line contains the integer sequence a1, a2,... an.
You can assume that all ai ∈ [1,n].
출력
Output the number of inverted triples.
입출력 예
입력
3
1 2 3
출력
0
입력
4
3 3 2 1
출력
2
출처: The 2011 Nordic Collegiate Programming Contest problem B
요약: tncks0121
[질/답]
[제출 현황]
[푼 후(2)]