kdhsong   3달 전

e5761199ea9c14064d51686356e7e13b.png


scpc 2차예선 3번 땅나누기문제입니다. 풀이를 보던도중이해가안가서 .. 

세그먼트트리는 알고있는데 최대 접두사 합은 " 왼쪽자식의 최대 접두사합"과 "왼쪽 자식의합 + 오른쪽 최대 접두사 합" 이라는 말이 이해가안가서요 ..설명좀부탁드릴게요고수님들 ㅠㅠ

chan4928   3달 전

리프가 아닌 노드의 최대 접두사 합으로 가능한 경우는

1. 왼쪽 자식이 가지고 있던 최대 접두사 합이 가장 큰 경우

2. 왼쪽 자식 전체의 합 + 오른쪽 자식이 가지고 있던 최대 접두사 합이 가장 큰 경우

두 가지로 볼 수 있습니다.

6b6ba533ee94dd9876657056a677f78a.png

kdhsong   3달 전

감사합니다..근데 이해가잘안되네요 접두사가어떤의미죠 ?.. 어떤책을봐야하나요 ?ㅠ

plzrun   1달 전

접두사: prefix를 얘기해요. 문자열에서 asdfgsdf 이런게 있으면 a, as, asd, asdf, asdfg, asdfgs, asdfgsd, asdfgsdf 모두 해당 문자열의 접두사인 셈이죠 ㅎ; 물론 이걸 물어보신거 같지 않아서 밑에 설명을 더 적어볼까 합니다.



같은 설명인데 좀 쉽게 해보자면


모든 점을 세그먼트 트리의 리프에 붙이는 거에요

가장왼쪽에 있는 리프노드는 x좌표 첫번째부분인거고

가장 오른쪽에 있는 리프노드느 x좌표 맨 끝에 있는 부분이에요


그 다음에 y가 가장 작은 순서부터 볼건데,

y가 작은 순서대로 올라가면서 파란색은 빨간색으로 색깔을 바꿔주고 빨간색은 파란색으로 색깔을 바꿔주면서

개수를 세면 됩니다. (y축 기준선을 0으로 잡고 쭈욱 올리면서 기준선 아래에 있는 색깔들을 모두 반전시킨다고 생각하시면 됩니다.)

그럼 y축기준선이 0이었을때는 왼쪽에 파란색만 세면 되고 오른쪽에는 빨간색만 세면 됐는데, 여기서 기준선을 찔끔 올려서 y축 기준선 아래에 어떤 점이 1개 들어가게 바뀐상태가 됐다면, 그 점의 색깔을 바꾼다는거죠. 그럼 y축 기준선 아래라는 것을 구분짓지 않고도 x축 기준선 왼쪽은 그냥 무조건 파란색 색깔만 세면 되고 오른쪽은 빨간색 색깔만 세면 됩니다.


그럼 여기서 포인트는 색깔을 바꿔주는 방법과 x축 기준선을 빠르게 구하는 방법입니다.

색깔 바꿔주기를 lgN만에 할 수 있고.. 이 업뎃을 하고나면 트리의 루트에서 바로 x축 기준선을 구할 수 있습니다. (얘는 그러니까 당근 O(1))

(말이 x축 기준선이지 그냥 왼쪽파랑이와 오른쪽 빨강이의 최대개수를 한방에 구할 수 있다고 생각하시면 됩니다.)



그니까 x좌표를 기준으로 왼쪽 파란점의 개수와 오른쪽 빨간점의 개수만 센다면..

그리고 그러한 최대값을 세그먼트 트리가 가지고 있다면 "(왼쪽.파랑이+오른쪽.빨강이)의 최대 개수"를 세그먼트 트리의 각 노드가 가지고 있는 셈이죠. => 이 개념이 세그먼트 트리에서 많이 쓰이는거 같아요.(왼쪽 자식의 A와 오른쪽 자식의 B의 최대나 최소를 계속해서 merge해 나가면서 루트가 그 정답을 가지고 있는 형태..)


그럼 (색깔 업뎃 O(lgN) + 트리에서 x축 기준선 구하기 O(1)) * y좌표 아래서부터 순서대로 다보기(N) 해서 O(NlgN)만에 구할 수 있습니다.



나머지 자잘한 시간단축은 fast I/O부터 해서 이거저거 시도해보시면 될 것 같아요.



근데 1달전이라 질문이라 이미 푸셨겠군요 ㅎ;

kdhsong   1달 전

@plzrun


아뇨! 딴거 준비하느라 포기하고있었는데 너무 친절하게 답변달아주셔서 꼭 다시 풀어봐야겠네요 ! 감사드립니다!!!!!!!~~~ㅎㅎ

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