[ICPC 본선 대비 뇌셋] Day 18

백준 2574번 마법색종이 www.acmicpc.net/problem/2574

2574번: 마법색종이

반도에 사는 초등학생의 위엄을 볼 수 있는 문제다. KOI 초등부 06년도 3번 문제인데, 지금까지 풀어본 바로 KOI는 좀 구현이 더럽거나 생각이 더러운 문제를 많이 내는거같다.

풀이는 여러가지가 있을 수 있는데, 두가지만 적겠다.

[풀이 1] 2D Seg

영역 더하기 쿼리를 진행하면 된다...

세그에서 더할 변수를 A, B로 두개를 잡는다. A는 그 블록의 인덱스를 나타내는 변수이며, B는 색깔을 나타내는 변수이다.

i번째 나누기 쿼리가 들어오면, i번째 점의 위치의 A값과 B값을 알 수 있다. B값의 홀짝성을 통해 가로줄 세로줄을 판단하고, (wlog 가로줄) 가로선에서 이분탐색을 통해 A값(인덱스)이 달라지는 부분을 찾는다. 마찬가지로 세로선에서도 이분탐색으로 A값이 달라지는 부분을 찾는다. 그러면 업데이트해야할 영역이 나오고, 이를 영역 더하기 쿼리를 통해 각 부분의 A값이 2i, 2i+1이 되도록 해준다. B값은 해당 영역 전체에 +1을 해준다.

모든 쿼리를 완료한 뒤, 리프노드에 대해서 영역을 전부 더해준다.

마지막으로 A에 따른 영역 합의 최대와 최소를 구해주면 된다.

$O(N lg(N)^3)$

무척 불안불안한 시간 복잡도다..

[풀이 2] Set을 이용한 풀이

처음 전체 영역을 루트로 하는 트리를 만든다.

각 노드는 set 배열 Sx[N], Sy[N], 그리고 자신의 영역(x1, y1, x2, y2)을 관리한다. 그리고 각 쿼리에 사용되는 점이 어느 인덱스의 셋에 있는지를 나타내는 배열 ind[N]을 잡는다.

노드들은 set의 포인터를 두 개씩을 관리하는데, 하나는 x방향 정렬 셋, 나머지는 y방향 정렬 셋이다. 처음 루트에 쿼리로 들어올 모든 점들을 Sx[0], Sy[0]에 삽입한다.

각 쿼리가 들어올 때마다 쿼리에 사용된 점이 어디에 있는지는 $k = ind[i]$를 통해 구해준다. 각 점이 속한 영역이 어떤색인지 아는 것은 쉬우니, 과정을 생략한다.

$Sx[k]$, $Sy[k]$에 대해서 가로선을 채워야한다면, Sx[k]에서 lower_bound(Q[i])를 찾고, Q[i]보다 큰 점의 갯수와 Q[i]보다 작은 점의 갯수중 무엇이 많은지를 구한다.(O(lg(N)*small_size)) 갯수가 더 적은 점들을 Sx[i], Sy[i]에 옮기고 트리의 셋의 셋의 포인터를 바꿔준다.

모든 쿼리를 완료한 뒤 리프 노드들에 대해서 넓이의 최댓값와 최솟값을 구해준다.

[시간복잡도 분석] 알고리즘 시간에 배운 유일하게 쓸모있던 시복 분석을 해보자!

$T(N) <= T(m)+T(N-m)+lg(N)*min(m, N-m)$

사실 분석은 안해봤지만, substitution method로 하면 대충 $O(Nlg(N)^2)$가 나올 것을 우리는 알고 있다.

시간복잡도: $O(Nlg(N)set(N))$

정풀이 뭘 의도한건지 사실 잘 모르겠다. 혹시 아시는 분 있으면 댓을 달아주시면 감사하겠습니다!