BOJ 25236 Triangular Logs
문제 내용
좌표평면 위에 그루의 나무가 자라 있습니다. 높이 인 나무를 자르면 길이 의 나무토막을 얻습니다.
각 변이 좌표축에 평행인 직사각형 영역이 개 주어질 때, 각각의 영역 내의 나무들 중에서 세 그루를 잘라 얻은 나무토막으로 면적이 0이 아닌 삼각형을 만들 수 있는지 판별하세요. 직사각형의 둘레에 걸쳐 있는 나무도 그 직사각형 내에 있는 것입니다.
입력
첫 줄에 과 가 주어집니다. ()
다음 줄에는 각 나무가 좌표, 좌표, 그 나무의 높이 순으로 주어집니다. ()
다음 줄에는 직사각형의 범위가 최소 좌표, 최소 좌표, 최대 좌표, 최대 좌표 순으로 주어집니다. ()
출력
각 쿼리에 대해, 삼각형을 만들 수 있으면 , 아니면 을 출력합니다.
문제 풀이
스포일러 (bungmint의 풀이)
먼저 나무들의 길이들의 목록을 알 때 답이 1인 조건을 생각해 봅시다. 정렬 순서로 연속한 3개씩만 확인해 보면 되며, 답이 0인 나무의 길이의 목록은 범위 내에서 45개를 포함할 수 없음을 알 수 있습니다.
일단 나무들을 좌표로 정렬하고, 각 나무의 좌표와 높이를 저장하는 세그먼트 트리를 만듭니다. 세그먼트 트리의 노드는 해당 구간 내의 모든 나무를 포함하는 멀티셋으로 둡니다.
이제 그 세그먼트 트리에 쿼리를 하였을 때 멀티셋을 서로 합칠 텐데, 쿼리의 파라미터에 좌표의 범위를 추가하여 각 멀티셋에서 좌표 조건에 맞는 것만 남깁니다. 그리고 목록의 길이가 45가 넘어가면 더 이상 원소를 추가할 필요가 없습니다.
이러한 쿼리의 결과의 길이가 45 이상이면 답은 1, 2 이하이면 답은 0, 그 외에는 나무의 높이들을 정렬하여 답을 확인해서 출력하면 됩니다.
스포일러 (bubbler의 풀이)
먼저 나무들을 좌표로 정렬하고, 모든 나무에 대해 자기 자신과 좌표가 그 이하인 것들을 1로 두는 비트셋을 만드는 것을 생각할 수 있습니다.
그러면 각 쿼리에 대해서 좌표 범위는 두 비트셋의 차집합을 구하고, 좌표 범위는 시간에 연속한 1이 켜진 비트셋을 생성할 수 있습니다.
이 비트셋 결과에서 1의 개수를 확인하여 1차로 판정을 하고, 1의 개수가 3개 이상 45개 미만일 경우에만 의 목록을 추출하여 답을 구할 수 있습니다.
그런데 개의 비트셋을 모두 만들어서 들고 있으면 메모리 제한을 아슬아슬하게 초과하므로, 적당히 작은 상수 를 잡아서 개의 비트셋을 만들고, 각 쿼리에 해당하는 비트셋은 이하의 추가 연산으로 구하는 방법을 쓰면 통과합니다.