좌표별로 압축한 다음에 2d seg tree를 잘 구축하시면 될 거 같아요.
처음에 구축하실 때가 문제인 거 같은데. 2d seg를 잘 생각해 보신다면
어떠한 범위가 있을 때.. [1]번째를 관리하는 seg 안에
[2]번째를 관리하는 seg가 들어가면 되지 않을까요..?? 결국 [1]번째를 관리하는 seg 안에 어떠한 값이 들어가느냐가 문제인데..
예를 들어 (2,2) (2,4) (4,7)이라는 게 있다고 해 봅시다. 그런 경우
seg[2 ~ 4]에는 [2,4,7]이라는 게 저장되어야 하겠지만
seg[2 ~ 2] 에는 y축 값이 [2,4]가 있다는 것이 저장되어야 할 거고, seg[4 ~ 4]에는 [7]이 저장되어야 하겠네요. 저는 그런 식으로 해서 풀었습니다.
jh20s 5년 전
M이 2일땐 LIS로 구하면 될 듯 싶고
M이 3일 때가 문제입니다.
제가 생각한 방법은 1행의 값을 기준으로 정렬을 해줍니다.
그리고 정렬된 값을 쭉 탐색해주면서 2,3행에 대해서 DP를 이용해 최댓값을 구해줄 겁니다.
DP[i] = max(0부터 i-1인 j에 대해 i.2행>j.2행 && i.3행>j.3행인 DP[j]) +1
이렇게 정의하려고 합니다.
문제는 2행을 x축, 3행을 y축이라 가정했을 때
x보다 작고 y보다 작은 값중 가장 큰 값 이런 쿼리를 구하고싶은 건데 방법을 모르겠습니다 ㅠ
어떤 방법이 있을까요