버블 소트는 수열에서 개의 인접한 짝 들을 비교해보면서 와 을 바꿔주고, 이와 같은 과정을 번 반복하는 의 정렬 방법이다. 정렬 과정에서 가장 처음에 번의 인접한 짝을 비교하면서 바꾸고나면 수열의 오른쪽 끝 에는 무조건 최댓값이 위치하게 된다. 번째 인덱스부터가 아니라 이 존재하던 위치부터 바꾼다고 생각해보자. 이 오른쪽 끝까지 오는데 몇 번의 swap이 일어났을까? 일때만 swap이 일어나므로 보다 오른쪽에 위치하는 수 중에서 보다 작은 수의 개수만큼 swap이 일어나게 된다.
의 모든 원소에 대해서 자기보다 오른쪽에 있는 작은 수의 개수를 의 과정으로 일일히 세준다면 으로 시간초과를 피할 수 없을 것이다. 우리는 의 원소를 크기가 큰 순서부터 순회한다면 자기보다 오른쪽에 있는 수는 모두 자기 자신보다 작다는 것에서 아이디어를 얻을 수 있다(확인한 후에는 자기 자신을 삭제). 이를 통해서 누적 합을 적용할 수 있다. 하지만 순회 과정중에서 자기 자신을 삭제해야하므로 update연산이 필요하다. 이를 세그먼트 트리르 이용해 구현할 수 있다.
구현을 간단히 하기 위해서 위에서는 의 원소를 크기가 큰 순서로 맨 오른쪽으로 보내줬지만 이를 의 원소를 크기가 작은 순서로 맨 왼쪽으로 보내줘도 문제는 동일하다.
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());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int[] S = new int[N];
for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
FenwickTree t = new FenwickTree(N);
for (int i = 1; i <= N; i++) t.add(i, 1);
// map[x] = x가 S의 몇번째에 있는지 반환 (1-based), x가 여러개일 수 있으므로 작은 것 부터
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
for (int i = 0; i < N; i++) {
PriorityQueue<Integer> pq = map.get(S[i]);
if (pq == null) map.put(S[i], pq = new PriorityQueue<>());
pq.offer(i + 1);
}
Arrays.sort(S);
long ret = 0;
for (int i = 0; i < N; i++) {
PriorityQueue<Integer> pq = map.get(S[i]);
while (!pq.isEmpty()) {
int x = pq.poll();
ret += t.sum(x) - 1;
t.add(x, -1);
}
}
System.out.println(ret);
}
}
class FenwickTree {
int[] tree;
FenwickTree(int n) { tree = new int[n + 1]; }
void add(int pos, int val) {
while (pos < tree.length) {
tree[pos] += val;
pos += (pos & -pos);
}
}
int sum(int pos) {
int ret = 0;
while (pos > 0) {
ret += tree[pos];
pos -= (pos & -pos);
}
return ret;
}
}