부분적으로 정렬 된 집합에 주어진 것보다 큰 값을 가진 요소 찾기

Question

유형의 요소 집합이 S입니다. T 유형의 요소에 부분 주문 <=이 있습니다. S의 모든 요소는 주문되지 않은 것으로 알려져 있습니다. 그러면 다음과 같은 쿼리를 수행하는 방법이 필요합니다. e이 T 인 인 경우과 같은 e'이 인 것을 확인하십시오.

선형 쿼리없이 S의 쿼리를 효율적으로 수행 할 수있는 데이터 구조가 있습니까?

중요 사항 : T은 완성 된 격자입니다.

Answer 1

목록을 전처리하고 해당 숫자보다 큰 다른 요소가없는 요소의 하위 집합을 찾을 수 있습니다 (모든 숫자를 대시로 나타내면 부모가없는 요소를 모두 찾아야 함). 해당 하위 집합을 가져 오면이 하위 집합에 대한 선형 스캔 만 수행하면됩니다. 나는 네가 이보다 더 잘할 수 있다고 생각하지 않는다.

또한이 하위 집합을 하위 집합의 이러한 요소 각각의 개수가 큰 순서로 정렬 할 수 있습니다. 그리고 요소를 순서대로 스캔하십시오.