pair로 LIS 하는 것

관련 문제

• https://www.acmicpc.net/problem/2532
• https://www.acmicpc.net/problem/23035

특징

• pair 들이 주어짐. 딱히 정렬된 상태는 아님
  • 그런데 어떤 문제에서는 나름의 기준으로 정렬된 pair를 처리해야 하는 경우도 있음(https://www.acmicpc.net/problem/15977)
    • https://chw0501.tistory.com/24 이분이 설명을 잘 해놓으심
    • 그런데 정작 난 저 문제를 평방 분할로 해결함......
  • 지금 다루려는 것은 저런 유형은 아님
• 작은 것들과 연결하는데, 그렇게 연결했을 때 길이가 가장 길었으면 좋겠음. LIS 비슷
  • 크기비교 : ${(y_1, x_1), (y_2, x_2) 일 때 y_1 <= y_2, x_1 <= x_2}$면, 작은 것임

아이디어

• 좌표의 범위가 크면 리라벨링을한다 => 하는 건 좋은데 그 다음 전략이 딱히 안떠오름
• 사각형을 탐색하면서 작업을 해야하나? => 수의 범위가 크면 ${N^2}$이 안됨
• 한쪽 값으로 일단 정렬을 해놓고 다른 값으로 찾아가면서 작은 범위에서 큰 값을 찾는 기법 => 구간트리 이용하는 기법

(나는)떠올리기 힘든 아이디어

• 한쪽 값은 오름차순(y), 다른 쪽 값은 내림차순으로 정렬함(x)
• x입장에서 살펴보면 나보다 앞에 나왔던 것들은 일단 y는 나보다 작을 것임
• 그 중에서 나보다 x가 작은 것들이 있을 텐데 그중에서 연결하기 가장 큰 것을 찾아 연결 = LIS를 lowbound로 해결하는 기법
• 그 다음에 나오는 x는 앞에 나온 x와 y가 같을 수도 있고 다를 수도 있음
  • y가 같은 경우 앞에 나온 x 보다 x는 작기 때문에 LIS를 해도 괜찮음 (만약에 컸다면 앞에 나온 결과로 인해 값의 갱신이 발생할 수도 있었겠지만, 그런 걱정은 안해도 됨)
  • y가 다른 경우는 상관 없음

참고

• https://codeforces.com/blog/entry/43319 에서 ko_osaga 님 댓글 참고