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보다 작은 값중 가장 큰 값  이런 쿼리를 구하고싶은 건데 방법을 모르겠습니다 ㅠ 


어떤 방법이 있을까요

chogahui05   5년 전

좌표별로 압축한 다음에 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년 전

2차원 세그를  고민해봤었는데 메모리 때문이 포기를 했습니다 ㅠㅠ

2차원 세그를 구현하려면 x축에 대해 1차원 세그를 만들어주고 이 1차원 세그 각 노드를 y축에 대한 2차원 세그로 만들어줘야할텐데

x축에 대한 값 20만개를 잡아주고 y축에 대해 20만개를 잡아주면 무조건 메모리초과가 뜰텐데... 

이걸 평방분할 느낌으로 루트로 줄일까 해봤는데 정확히 xi,yi이하의 값을 찾아야해서 이것도 불가능해보입니다.

음 죄송하지만 조금만 구체적으로 y에 대해서 어떻게 저장되는지 알려주실수있을까?ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.