Inversion Counting
Prerequisite
- Segment Tree or Fenwick Tree
- Merge Sort
Inversion Counting
Inversion Counting은 원소의 종류는 같고 순서만 다르게 배치되어 있을 때, $f(x)$ 로 선을 그으면 특정 두 원소간에 순서가 교차하는 것의 개수이다.
문제에 따라 수의 중복이 있을 수 있다. 그에 따라 구현을 적절히 신경써줘야 한다.
위와 같은 그림에서 각 선분이 교차하는 부분의 개수이다.
이걸 이용하면 다양한 문제를 해결할 수 있는데, 그건 이따 살펴보고 이 개수를 어떻게 세는지 먼저 살펴보자.
구간합 트리로 세기
구간합 세그먼트 트리나 펜윅 트리를 이용해 세줄 수 있다.
위의 그림을 이용해 세준다고 해보자.
일단 1에서 1로 갔고 아래쪽에 방문되었다는 표시의 체크를 했다.
이제 2에서 2로 갈건데, 이 때는 기존 1과 교차하게 된다.
이 때, 바로 $f(2)$ 에서 끝 까지 체크되어있는 것의 개수를 정답에 더해줌으로써 교차하는 것의 개수를 셀 수 있다.
이런 방식으로 끝까지 세주면 되고 이를 구간합 트리로 구현하면 된다.
구간합 쿼리가 $O(\log N)$ 이라고 할 때, 결국 끝까지 모두 세면 $O(N\log N)$ 이 걸린다.
병합 정렬로 세기
$f$ 를 다시 기존 수열로 되돌리는 정렬 과정에서 병합 정렬을 사용하면 이 수를 세줄 수 있다.
두 배열을 합칠 때 더 오른쪽에 있던 배열 $R$ 의 원소 $r$ 이 합쳐져야 할 배열 $T$ 의 다음 자리로 갈 때, 왼쪽에 있던 배열 $L$ 에서 아직 $T$ 로 가지 못한 원소의 수를 정답에 세주는 것이다.
병합 정렬은 $O(N\log N)$ 이므로 이 때도 시간복잡도는 같다.
정렬된 두 배열 $L$ 과 $R$ 이 있고 $L=\{1,4,5,7\} ~~ R=\{2,3,6,8\}$ 라고 하자.
병합 정렬 과정에서 다음과 같이 진행된다.
$L={\color{salmon}1},4,5,7~~R=2,3,6,8\\T=1$
이건 $L$ 에서 $T$ 로 이동한 것이므로 정답을 세주지 않는다.
이제 $R$ 에서 $2$ 가 $T$로 이동한다.
$L={\color{salmon}1},4,5,7~~R={\color{salmon}2},3,6,8\\T=1,2$
이 때, $L$ 에는 아직 이동되지 못한 원소 $3$ 개가 있으므로 정답에 3을 더해준다.
이 이동하지 못한 원소들은 언젠간 $T$ 로 갈텐데 그럼 $R$ 에서 먼저 $T$ 에 가있었던 $2$ 와 계속 한 번씩 교차될 것이기 때문에 세주는 것이다.
$L={\color{salmon}1},4,5,7~~R={\color{salmon}2, 3},6,8\\T=1,2,3$
정답에 또 3이 더해진다.
$L={\color{salmon}1,4},5,7~~R={\color{salmon}2, 3},6,8\\T=1,2,3,4$
$L={\color{salmon}1,4, 5},7~~R={\color{salmon}2, 3},6,8\\T=1,2,3,4,5$
이번엔 두개가 $L$ 에서 왔으므로 정답은 그대로이다.
$L={\color{salmon}1,4, 5},7~~R={\color{salmon}2, 3,6},8\\T=1,2,3,4,5,6$
정답에 $L$ 에 남은 원소의 수 1을 더해주게 되고,
$L={\color{salmon}1,4, 5,7}~~R={\color{salmon}2, 3,6,8}\\T=1,2,3,4,5,6,7,8$
더 교차되는 것 없는채로 알고리즘이 종료된다. 총 inversion counting 횟수는 $7$ 이다.
이를 구현한 코드는 다음과 같다.
vi a = {1, 4, 5, 7, 2, 3, 6, 8};
int ans = 0;
function<void(int, int)> merge_sort = [&](int l, int r) -> void {
if (l >= r) return;
int m = l + r >> 1;
merge_sort(l, m);
merge_sort(m + 1, r);
vi T(r - l + 1);
for (int i = l, j = m + 1, t = 0; t < sz(T); t++) {
if (j == r + 1 || (i != m + 1 && a[i] < a[j])) T[t] = a[i++];
else {
T[t] = a[j++];
ans += m + 1 - i; // here
}
}
for (int i = 0; i < sz(T); i++) a[l + i] = T[i];
};
merge_sort(0, sz(a) - 1);
활용 1 - Inversion Counting 세기
정말 말 그대로 Inversion Counting을 세는 문제들도 많다.
BOJ 10090 - Counting Inversions 도 있고,
BOJ - 7578 를 보자.
배치가 이렇게 되어있고 교차하는 선 쌍의 수를 세라는 문제이다.
펜윅 트리를 이용해서 풀면 다음과 같다.
int n;
cin >> n;
vi a(n), b(n);
fv(a);
fv(b);
vi compress = a;
uniq(compress);
for (int &i: a) i = lbi(compress, i);
for (int &i: b) i = lbi(compress, i);
vi to(n), idx(n), tree(n + 1);
for (int i = 0; i < n; i++) idx[a[i]] = i;
for (int i = 0; i < n; i++) to[idx[b[i]]] = i;
ll ans = 0;
for (int i = n - 1; i >= 0; i--) {
int j = to[i] + 1;
while (j) {
ans += tree[j];
j -= j & -j;
}
j = to[i] + 1;
while (j <= n) {
tree[j]++;
j += j & -j;
}
}
cout << ans;
구간합 쿼리를 이용해 Inversion Counting을 세줄 때, $0 \to n-1$ 로 가는게 아닌 $n-1 \to 0$ 으로 가면 뒤에 체크된 것을 세는게 아닌 앞에 체크된 것을 세는 구현으로 바꿀 수 있기 때문에 쿼리를 $[0,\,to_i]$ 의 구간합을 구하면 되기 때문에 편하다.
활용 2 - 순열의 기우성
$\sigma(x)=x$ 인 순열 $\rm P$ 에서 어떤 순열 $\rm Q$ 로 변환하기 위해 임의의 두 원소 $x,\,y~~\small (x\ne y)$ 를 스왑하는 연산을 할 때, 그 연산의 횟수는 $\rm Q$ 에 따라 항상 홀수이거나 항상 짝수이다.
그리고 이것의 기우성은 Inversion Counting의 기우성과 동치이다.
이 블로그 에서 증명을 참고할 수 있다.
하지만 순열의 기우성을 구하는 것이 꼭 Inversion Counting으로 구현되어야 하는것은 아니고 짝수 길이의 싸이클을 찾는 것으로 $O(N)$ 에 수행될 수도 있으니 참고하자.
PS에선 이러한 성질을 이용해 어떤 순열 $\rm Q$ 에서 어떤 순열 $\rm R$ 로 위와 같은 연산을 통해 도달 할 수 있는지를 물어보는 문제들이 있다.
대표적으로 BOJ 5000 - 빵 정렬 이 있다.
이러한 문제들의 특징은 문제에서 설명하는 연산이 결국 위 연산과 동치라고 보아도 무방하다고 증명하기 어렵게 만들어 두었다는 점이다.
예를 들어, 어떤 연산 $\sigma$ 를 $0$번 이상 할 수 있는데, $\sigma$ 가 결국 임의의 두 원소를 스왑하는 연산을 짝수번을 하는 것과 동치라든지 하는것을 보이는 것이 쉽지 않을 수도 있다.
짝수번을 스왑하면 기우성이 변하지 않기 때문이다.
물론 짝수번 스왑하는 것이 임의의 두 원소를 교체하는 연산 두번을 하는것과는 엄연히 다르지만 결국 문제 by 문제기 때문에 이 연산을 가한다는 행위가 기우성을 판단하는 것과 연관이 있다는 것을 캐치해내면 된다.
증명
왜 순열의 기우성과 Inversion Counting의 기우성이 동치인지를 증명한다.
임의의 순열 $\rm P$ 이 $\rm P_a\cdots P_b \cdots P_c$ 라고 할 때, $a$ 와 $c$ 를 교환한다고 했을 때 $i<a$ 거나 $i>c$ 인 $i$ 는 영향받지 않는다.
이 수열의 Inversion counting이 $I$ 라고 할 때, $\rm P_a<P_c$ 라면 $I$ 가 $1$늘어나고 반대라면 $1$감소가한다.
임의의 $b~(a<b<c)$ 에 대해 $\rm P_a<P_b$ 였다면 $I$ 가 $1$늘어나고 반대라면 $1$감소한다. $\rm P_b < P_c$ 라면 $I$ 가 $1$증가하고 반대라면 $1$감소한다.
따라서 $a$와 $c$ 사이의 모든 원소들은 $a,\,c$ 의 교환으로 인해 $I$ 에 $\lvert 2 \rvert \text{ 혹은 } 0$ 의 영향을 미치므로 $I$의 기우성에 영향을 주지 않고 오직 $a,\,c$ 만이 기우성에 영향을 줘 한 번의 교환으로 기우성이 무조건 변하게 된다는 것이 보여진다.
$\sigma(x)=x$ 인 순열 $\rm P’$ 에서 시작해 $\rm P$ 로 가는 교환 과정을 거치면 $I$ 의 기우성과 $\rm P$의 기우성이 동일하게 바뀌므로 $\rm P$의 기우성과 $I$ 의 기우성은 동치이다. $\blacksquare$
Comments