버블 소트는 인접한 두 원소를 바꿔주는 정렬 방법이었는데 이렇게 세 원소를 골라주는 방법은 어떨까?
문제의 조건이 비슷하므로 Inversion을 구하는 과정과 비슷하게 풀 수 있을 것 같다.
가 가지고 있는 Inversion의 수
이렇게 정의하자. 단, 쌍에서 가 라고 해서 중복으로 세지지 않게 하자.
즉, 는 에서 보다 왼쪽에 있으면서 보다 큰 순서쌍의 개수이다.
예를 들어 이라면 이다.
여기에 까지 추가해서 우리가 구하고자 하는 세 원소를 구해보자. 보다 왼쪽에 있는 Inversion의 개수들을 모두 더하면 조건을 만족하는 순서 쌍의 개수를 모두 구할 수 있다. 가능한 모든 경우를 세기 위해서는 가장 작은 부터 찾아봐야하는데, 두 원소의 값이 같은 경우가 있으므로 그런 경우는 같은 원소중에서 더 왼쪽에 있는 것 부터 먼저 체크해주도록 하자.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] S = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
// P[x] = S의 원소 x의 위치 (작은 순으로)
ArrayList<PriorityQueue<Integer>> P = new ArrayList<>();
for (int i = 0; i <= N; i++) P.add(new PriorityQueue<>());
for (int i = 0; i < N; i++) P.get(S[i]).add(i + 1);
long[] I = new long[N + 1]; // S[i]가 가지고 있는 Inversion의 개수 저장
FenwickTree t = new FenwickTree(N); // S[i]가 존재하는지 여부
for (int i = 1; i <= N; i++) t.add(i, 1);
// I[i]를 만든다
for (int i = 1; i <= N; i++) {
PriorityQueue<Integer> pq = P.get(i);
// PriorityQueue를 순회하기 위해 임시로 만듬
PriorityQueue<Integer> temp = new PriorityQueue<>();
while (!pq.isEmpty()) {
int x = pq.poll();
// t에 남아있는 모든 원소는 S[x]보다 같거나 크고,
// 같은 원소들은 S[x]보다 오른쪽에 있으므로
// 구간 합 t[x] - 1은 Inversion의 개수가 된다.
I[x] = t.sum(x) - 1;
t.add(x, -1);
temp.offer(x);
}
P.set(i, temp);
}
long sum = 0;
t = new FenwickTree(N);
for (int i = 1; i <= N; i++) t.add(i, I[i]);
for (PriorityQueue<Integer> pq : P) {
while (!pq.isEmpty()) {
int x = pq.poll();
sum += t.sum(x - 1);
t.add(x, -(t.sum(x) - t.sum(x - 1)));
}
}
System.out.println(sum);
}
}
class FenwickTree {
long[] tree;
FenwickTree(int n) { tree = new long[n + 1]; }
void add(int pos, long val) {
while (pos < tree.length) {
tree[pos] += val;
pos += (pos & -pos);
}
}
long sum(int pos) {
long ret = 0;
while (pos > 0) {
ret += tree[pos];
pos -= (pos & -pos);
}
return ret;
}
}
개의 원소들에 의 연산을 하므로
100000
100000 99999 99998 ... 3 2 1
->166661666700000
현주가 만든 불만 정렬은 10만개의 원소를 정렬하는데 이만큼 비교를 해야한다... 이 테스트 케이스에서는 어떤 세 원소를 고르더라도 조건을 만족하므로 의 결과와 같다는 것도 알 수 있다.