7578. 공장

7578번: 공장

---

$N$개의 기계가 일렬로 배치되어 있다. 기계의 배열에서 케이블이 교차하는 횟수를 세야 한다.

 

우선 문제를 간단하게 모델링하자. 식별 번호 대신 1부터 시작하는 인덱스를 부여하고, $pos[i]$를 A열의 $i$번째 기계가 연결된 B열의 기계의 위치로 정의하자. 예제 1을 예로 들면 $pos$ 배열은 다음과 같다.

3 1 4 2 5

케이블이 꼬여 있다는 것은 두 케이블의 상대적인 방향이 다르다는 뜻이다. 이 조건은 $i<j$일 때 $pos[i] > pos[j]$라는 식으로 표현할 수 있다. 이 식을 ``inversion of array``라고 한다. 

 

이제 $pos[i] > pos[j]$를 만족하는 $i,~j~(i < j)$ 쌍이 몇 개인지 세어야 한다. 그런데 $N \le 500,000$이므로 $O(N^{2})$ 방법을 사용하면 시간 초과다. 로그 시간 이하의 방법을 찾아야 한다.

---

펜윅 트리를 이용하여 ``inversion``의 수를 빠르게 찾을 수 있다. 펜윅 트리는 부분 합을 빠르게 구할 수 있는 자료구조이다. 배열 $arr$에 대해 다음의 두 가지 연산을 정의한다.

 

• $sum(i)$: $[1, i]$ 구간의 합을 반환
• $add(i, x)$: $arr[i] = arr[i] + x$, 즉 $arr[i]$를 $x$만큼 증가시킨 후 부분합을 갱신

이 글에서 구현까지는 다루지 않겠다.

 

$arr$의 초기 상태는 길이가 $N+1$이고 값이 모두 $0$인 배열이다. $0 \le j < n$각 $j$에 대해 다음의 알고리즘을 수행한다.

1. $ans += j - sum(pos[j])$
2. $add(pos[j], 1)$

식의 의미를 하나씩 파헤쳐 보자.

 

• $j$는 $j$번째 수를 제외하고 지금까지 본 수의 개수이다.
• 과정 2번에서 각 $pos$에 $1$을 더하는데, 이는 해당 값이 등장했다는 표시를 해준 것이다. 따라서 $sum(pos[j])$는 지금까지 본 $j$개의 수 중 $pos[j]$보다 작은 수의 개수이다. 이것은 ``inversion``의 정의와 정확히 반대된다.
• $j - sum(pos[j])$는 지금까지 본 $j$개의 수 중 ``inversion``에 속하지 않는 수의 개수를 빼어 ``inversion``의 개수를 구하는 식이다. 따라서 정답은 $\sum_{j=0}^{n-1}{j-sum(pos[j])}$이다.

---