mic1021   9달 전

이 문제 할 때 plane sweeping 쓰는 건 알겠습니다. x축을 따라서 지도가 있는 넓이를 더해주는 식으로 구현하려고 했더니 문제가 생겼습니다.특정x값에서의 전체 y범위 중  특정y범위는 지도가 겹치는 부분일테고 어떤 y범위는 아예 지도가 없는 부분일 테고 어떤 y범위는 지도가 하나있는 부분일텐데 이런 정보들을 segment tree내에 어떻게 저장해야 되는지가 고민입니다.  

ntopia   9달 전

지금 이 소스 안에서 설명을 드리자면

세그먼트 트리에다가 왼쪽 변이 등장하면 +1, 오른쪽 변이 등장하면 -1 을 하고 있는 것 같은데,

우리는 합집합의 넓이를 구해야 하잖아요?

생각해보면 세그먼트 트리에서 값이 0보다 큰 부분이면 정사각형이 하나 이상은 덮인 곳이겠죠?

이 부분들의 개수를 세서 (now-prev) 와 곱하면 될 것 같습니다.

세그먼트 트리 업데이트 할 때 0보다 큰 부분의 개수를 세는 코드를 추가해야 겠네요...

mic1021   9달 전

만약 기존에 1~3 과 7~8이 채워진 상황에서 1~9가 채워지면 1~3과 7~8은 두번 겹치고 4~6과 9는 한번만 채워진 상황일텐데요

이 때 1~9구간에 해당하는 seg_tree배열값에 +1 해주는 게 맞나요? 아니면 1~9 아래로 내려가서 1~3이랑 4랑 5~6이랑 7~8이랑 9에 각각 +1해주는게 맞나요?

mic1021   9달 전

예를 들어서 1~9구간에서 -1 해야 되는데 1~4 와 7~9는 두번 겹친 상황이고 5~6은 하나만 있는 상황 일 때는 seg_tree배열의 1~9구간에 해당하는 값에서 -1해주면 안되잖아요? 그래서 아래로 내려가라는 표시로 seg_tree배열의 1~9구간에 해당하는 값을 -1로 설정했는데요.. 이런식으로 계속 내려가게 되면 재귀호출의 수가 증가해버려서 시간초과가 뜨게 됩니다... 

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