전깃줄의 시작점/도착점 쌍이 주어져있을 때, 최소의 전깃줄만 제거하여 서로 겹치지 않게 하는 방법을 출력하는 문제입니다. ① 2565 - 전깃줄 문제와 같은 문제이지만 그 문제의 규모와 출력 방식에 있어서 큰 차이가 있습니다. 2565번 문제는 제거해야할 전깃줄의 수만 출력하면 됐지만 이 문제는 그 방법도 출력해야하며, 전깃줄의 개수가 100개에서 100000개로 늘어났습니다. 대충 짐작해보면 $O(n^2)$ 미만의 시간복잡도를 가진 알고리즘을 사용해야합니다. 이 때 사용할 수 있는 방법이 LIS를 $O(n\log n)$에 구하는 것입니다.
$O(n\log n)$에 LIS를 구하는 방법은 길이가 i인 LIS가 있을 때, 그 마지막 원소의 최소값의 배열을 계속 저장해나가는 방법을 사용할 수 있습니다. 그리고 새 원소에 대해 이분 탐색으로 배열에 인덱스 j에 대해 j보다 작고 j-1보다 큰 원소가 있으면 그 자리를 새 원소로 대체합니다. 여기까지는 $O(n\log n)$ LIS를 구하는 방법과 같은데, 이 원소가 LIS에 속할 때 그 이전 원소를 같이 저장하면 LIS의 정보까지 저장할 수 있습니다. 이제 LIS에 포함되지 않는 원소를 모두 출력하면 됩니다. 사실 글로 설명하니까 하나도 이해가 안 갈 것 같아서 그만뒀다 카더라 본인도 잘 아네
PS알못 OrbitHv의 PS