BOJ32766 색깔 사각형과 쿼리

https://www.acmicpc.net/problem/32766

 

이런 형태의 문제는 우선 트리를 만들고 생각하고 싶다. 각 직사각형의 외부 중 가장 가까운 직사각형을 그 직사각형의 부모라 하자. 모든 직사각형을 포함하는 직사각형을 추가해주면, 이 직사각형을 루트로 하는 하나의 트리가 생긴다.

 

그럼 쿼리에서 물어보는 것이 무엇일까? 트리에서 쿼리로 주어진 점을 포함하는 직사각형 중 깊이가 가장 작은 정점을 잡아보자. 그럼 트리에서 경로 쿼리가 된다. 트리의 어떤 정점에서 부모로 가는 간선은 그 정점에 해당되는 직사각형이 가지고 있는 색 중 적어도 하나를 지나야 한다는 관찰도 할 수 있다.

 

이때 색은 $6$가지기 때문에, 트리의 경로 중 임의의 색 조합만 지나는 경로가 존재하는지에 대한 문제를 $2^6$번 해결하는 방법이 있다. 각 문제는 유니온 파인드를 통해 해결해줄 수 있다. $\mathcal{O}(2^C (N + Q))$가 된다 ($C$는 색의 개수).

 

트리를 만드는게 제일 어려웠다. 나는 세그에 std::set을 넣어서 스위핑을 했다. 그럼 총 시간복잡도가 $\mathcal{O}((N + Q) \log^2 N + 2^C(N + Q)$가 되는데, std::set 연산이 상당히 무겁기 때문에 그냥은 tl에 돌지 않는다. 세그 대신 펜윅에 std::set을 넣으면 어느정도 돌만해진다.

 

jyheo98님이 알려주신 똑붙 방법으로는 로그에 된다. 지금 추가한 선분의 윗 부분이 천장이라면 외부는 그 사각형이 되고, 만약 바닥이라면 그 사각형의 외부고 지금 선분의 외부가 된다.

 

전체적으로 구현이 힘든 문제였다..