[BOJ 20190] 버블버블

 

[문제]

 

www.acmicpc.net/problem/20190

20190번: 버블버블

 

 

[난이도]

 

- Platinum II (20.12.28 기준)

 

 

[필요 개념]

 

 - Lazy Propagation

 - Segment Tree / Fenwick Tree

 

 

[풀이]

 

올해 koi 중등부 2차 문제이다. 

중등부에 이런 난이도 문제가 나온다는 거에 한 번 놀랐고, 이 문제 만점자가 4명이나 된다는 거에 두 번 놀랐다. 

이 문제를 보고 lazy propagation을 떠올리기도 힘들었고, lazy propagation을 이용한다는 걸 아는 상태에서도 풀이를 떠올리기 힘들어 koi 공식 해설지를 참고했다.

 

먼저, 수열을 버블정렬할 때 필요한 최소 교환 횟수는 Inversion Counting 이라는 유명한 문제이다. 

i < j && A[i] > A[j] 를 만족하는 모든 순서쌍 (i, j)의 개수를 구하는 것과 동일하다. 

이를 구하는 방법은 Merge sort와 구간 트리가 있는데, 이 글에서는 Fenwick Tree로 먼저 구해두었다. 

 

그다음, 각 원소마다 값을 바꿨을 때 교환 횟수가 최소가 되는 값을 찾아주어야 한다. 

핵심적인 아이디어는 다음과 같다. 

 

i번째 원소인 A[i]를 바꾸는 경우에 대해서 생각해보자.

j < i인 A[j]에 대해서, A[i]는 [1, A[j]-1]의 값이면 counting이 1 증가하고, [A[j], X] 의 값이면 증가하지 않는다. 

j > i인 A[j]에 대해서는, A[i]가 [A[j]+1, X]의 값이면 counting이 1 증가하고, [1, A[j]]의 값이면 증가하지 않는다. 

 

따라서 먼저 각 원소에 대해서 [A[i]+1, X] 구간에 1씩 다 더해준다. 

이 의미는 제일 앞에 원소를 새로 추가한다고 가정하면, A[k] > A[i]를 만족하는 i의 개수를 구하려면 트리의 [A[k], A[k]]의 값을 구하면 된다는 것이다. 즉, 추가되는 counting inversion의 수이다. 

 

그다음 첫 번째 원소부터 차례대로 교환 횟수가 최소인 값을 구한다. 

교환 횟수가 최소가 되는 값은 구간 트리에서의 최솟값이므로 lazy propagation을 이용한 최솟값 세그먼트 트리를 이용하여 구한다. 

우선 [A[i]+1, X] 구간에 -1씩 더해주어 현재 원소를 제거해준다.

그리고 기존의 원소에 의해서 더해지는 inversion count를 빼고, 최소의 inversion count가 추가되는 값을 더해주면 답이 된다. 

 

현재 원소의 결과를 구하고 나면 [1, A[i]-1] 구간에 1씩 더해주어 후에 i < j && A[i] > A[ij인 경우들을 고려하게 한다. 

그리고 [A[i]+1, X] 구간에 -1씩 더해주어 i < j && A[i] < A[j]인 경우들을 고려하지 않게 한다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define ini(x, y) memset(x, y, sizeof(x));
#define pb push_back
using namespace std;
using ll = long long;
const int MAX = (int)2e9;

int A[300001];
int tr[1200001];
int lazy[1200001];
int N;
void update_lazy(int x, int s, int e);
int sum(int i) {
	int ans = 0;
	while (i > 0) {
		ans += tr[i];
		i -= (i & -i);
	}
	return ans;
}
void update(int i, int val) {
	while (i <= N) {
		tr[i] += val;
		i += (i & -i);
	}
}
void update_range(int x, int s, int e, int l, int r, int val) {
	update_lazy(x, s, e);
	if (s > r || e < l) return;
	if (s >= l && e <= r) {
		tr[x] += val;
		if (s != e) {
			lazy[x * 2] += val;
			lazy[x * 2 + 1] += val;
		}
		return;
	}
	update_range(x * 2, s, (s + e) / 2, l, r, val);
	update_range(x * 2 + 1, (s + e) / 2 + 1, e, l, r, val);
	tr[x] = min(tr[x * 2], tr[x * 2 + 1]);
}
void update_lazy(int x, int s, int e) {
	if (lazy[x] != 0) {
		tr[x] += lazy[x];
		if (s != e) {
			lazy[x * 2] += lazy[x];
			lazy[x * 2 + 1] += lazy[x];
		}
		lazy[x] = 0;
	}
}
int min_(int x, int s, int e, int l, int r) {
	update_lazy(x, s, e);
	if (s > r || e < l) return MAX;
	if (s >= l && e <= r) return tr[x];
	else return min(min_(x * 2, s, (s + e) / 2, l, r), min_(x * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		v.push_back(A[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(all(v), A[i]) - v.begin() + 1;
	}
	ll bubble = 0;
	for (int i = N; i >= 1; i--) {
		bubble += sum(A[i] - 1);
		update(A[i], 1);
	}

	ini(tr, 0);
	int s = 0;
	int e = N + 1;
	for (int i = 1; i <= N; i++) {
		update_range(1, s, e, A[i] + 1, e, 1);
	}
	for (int i = 1; i <= N; i++) {
		update_range(1, s, e, A[i] + 1, e, -1);
		int pre = min_(1, s, e, A[i], A[i]);
		int post = min_(1, s, e, s, e);
		cout << bubble - pre + post << ' ';
		update_range(1, s, e, s, A[i] - 1, 1);
	}
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^