• KOI 초등부 문제로 출제되었던 문제이다. 세상에..
• 그냥 단순한 구현은, 색종이 조각들을 이진트리 형식으로 만드는 것이다. 각 리프노드가 잘라진 조각 한개한개가 된다. 점이 입력될때마다, 이진트리를 탐색해서 점이 포함된 조각에 해당되는 노드를 찾고, 그 조각을 분할해서 생기는 조각 두개를 차일드 노드들로 만드는 것을 반복하면 된다.
  • 느낌상으로는 초등부 문제로써는 이것이 정해였을것 같다.. 하지만 이렇게 하면 트리가 최대로 skew되어있을경우 시간복잡도가 O(n^2)이 걸린다. 그리고 질문 게시판에는 O(n^2) 솔루션을 저격하기 위해 추가 요청을 한 데이터들이 많이 보인다..
• 다른 방법을 생각해보자. 오프라인 쿼리의 아이디어가 필요하다.
• 각 색종이 조각이 조각 안에 포함되는 점들을 저장하도록 구축한다. 그리고 각 조각마다 조각에 포함된 점들중 가장 쿼리 순서가 빠른 점을 찾아서, 시키는대로 두개의 조각으로 분할한다. 당연히 갖고있던 점의 집합도 둘로 분할하면 된다. 이 방법을 잘 구현한다면 시간복잡도를 좀더 줄일수 있다. 하지만 이것을 효율적으로 구현을 하는것이 그리 간단하지는 않다.
• 찾은 해결방법은 두가지이다. 이중 실제로 구현해 본것은 Small to large원리를 사용하는 두번째 방법만이다.
• 첫번째 방법은 2d 세그먼트 트리를 이용하는 방법이다. 조각이 명시적으로 점의 집합을 갖고 있는 대신에, 조각에 해당되는 영역 내에서 가장 쿼리순서가 작은 점을 2d 세그먼트 트리로 찾을 수 있게 하는 것이다. 2d 세그트리만 미리 짜 놓았다면, 나머지는 비교적 간단하게 구현 가능할것 같다. (하지만 2d 세그트리가 없어서 이 방법은 실제로 구현하지는 않았다..). 한번 분할할때마다 O(log^2N)의 min 쿼리를 날려야 하고, N번의 분할이 필요하므로 대충 O(Nlog^2N)의 시간에 처리가 가능하다
• 두번째 방법은 진짜로 각 조각이 자신의 점 집합을 관리하게 하는 것이다. 두 조각으로 분할할 때, Small to large원리를 적용하는 것이 핵심이다. 원래 집합이 큰집합과 작은집합으로 분할될때, 작은집합에 해당되는 원소들만 이동시키는 것으로 처리하면, 이동 횟수를 O(NlogN)으로 유지할 수 있다.
• 어려운점은 이것을 처리하기 위해서 집합에서 서포트해줘야 하는 연산이 다양하다는 것이다. 우선 집합에서 가장 쿼리 순서가 작은 점을 찾을수 있어야 한다. 또한 집합에서 x좌표가 X이하인 점들 M개를 삭제하고 새로운 집합에 삽입하는 것을 O(f(M))에 처리할 수 있어야 한다. y 좌표에 대해서도 마찬가지.
• 그러면 쿼리 순서, x좌표, y좌표의 정렬 기준으로 다 연산이 가능해야 하기 때문에, 똑같은 점들을 비교 기준이 다른 세개의 ordered set에 저장하는 것을 생각할 수가 있다. 이렇게 저장한다면 해야하는 작업은 다음처럼 바뀐다. 쿼리순서를 기준으로 하는 set에서 가장 작은 점을 찾고, 그 다시 x좌표를 기준으로 하는 set에서 그 점보다 x좌표가 작은 점의 갯수와 그 점보다 x좌표가 큰 점의 갯수를 비교한다. 그중에서 갯수가 작은쪽에 해당되는 점 M개를 찾고, 그 M개의 점을 세개의 set에서 모두 삭제하고, 새로 만든 조각에 있는 세개의 set에 다시 삽입한다.
• 각 set에서 처리해야 하는 연산은 '가장 작은 값 찾기', 'X보다 작은 값의 갯수 찾기', 'X보다 작은 값을 모두 찾기', '특정 원소를 삭제하기', '특정 원소를 삽입하기' 이다. 잘 만든 BBST를 이용하면 'X보다 작은 값을 모두 찾기'는 O(M)에, 나머지는 O(logN)에 연산이 가능하고, c++에는 pb_ds에 다 구현이 되어있다. 이렇게 구현하면 O(NlogN)개의 원소 이동이 필요하고, 이것은 O(logN)삭제와 삽입연산으로 처리되므로 총 O(Nlog^2N)에 해결이 가능하다.
• 하지만 파이썬에서는 내장 BBST가 없기 때문에 새로 만들어서 써야 한다. teflib.segmenttree.OrderStatisticTree는 메모리를 숫자 범위만큼 먹기 때문에 O(N)개의 인스턴트를 만들어야 하는 이 문제에서는 사용이 불가능하다. 이럴때 쓰기 위해서 트립(teflib.treap.Treap)을 구현해 두었지만, treap으로 구현한 결과 TLE가 나버렸다 ㅜㅜ
• 고민끝에 생각한 것은 내장 dict. python 3.7부터는 dict가 삽입된 순서대로 순서를 유지한다. 여기에서는 처음에 집합이 만들어지고 나면, 그 이후에는 삭제만 필요하고 추가 삽입은 일어나지 않기 때문에, 처음에 dict를 만들때, 원하는 순서대로 정렬해서 삽입시켜주는 것으로 필요한 속성을 유지할 수 있다. 이 dict에서 'X보다 작은(또는 큰) 값을 모두 찾기'는 X값이 나올때까지 앞에서(또는 뒤에서)부터 iteration하는 것으로 처리 가능하다. 'X보다 작은 값의 갯수 찾기'를 O(logn)에 해결할수 있는 방법이 없다는 것이 조금 곤란한 점이기는 한데, 'X보다 작은 값의 갯수' 와 'X보다 큰 값의 갯수'중 작은 것을 찾는 것으로 생각하면, 양쪽 끝에서 동시에 iteration 하면서 먼저 X를 만나는 쪽이 더 작은 집합이라고 생각할수 있다. 그러면 O(M)에 찾을수 있다. 이동시켜야 할 M개의 점을 찾은 다음에는 점들을 쿼리순서,x좌표,y좌표 세가지 기준으로 정렬한다음에 새로운 집합에 추가한다. 소팅하는데에 O(MlogM)시간이 필요하지만, 점을 추가/삭제하는 것이 O(1)에 되기 때문에, M개의 점을 이동시키는 것은 bbst를 쓸때와 마찬가지인 O(MlogM)에 처리된다. 결국 총 시간 복잡도는 동일하게 O(Nlog^2N)에 처리가 된다.
• 쿼리순서대로 점을 저장하는 집합만 놓고 보면, 항상 최소값을 구하는 연산만 필요하기때문에 priority queue로 만들어도 가능하고 그편이 더 빠를것이긴 하다. 하지만 어차피 다른 집합들에는 적용이 불가능하므로 그것만으로는 속도 향상에 한계가 있을 것이라서 구현은 안했다.

(다이아몬드 이상은 코드 생략)