noeffserv   5달 전

저는 이 문제를 lazy propagation 으로 접근해서 풀고 있는데요 계속 시간초과를 넘어서질 못하네요 힌트를 조금 얻고 싶습니다

choiking10   5달 전

저도 segment tree의 lazy propagation을 사용해서 풀었는데 어쎕이 났습니다. 어떤 부분이 시간초과를 내는지 잘 모르겠네요 ㅠㅠ 

appa   5달 전

전 버킷 써서 풀었어요.

이 문제 lazy update할 때 짝수이면 0, 홀수이면 lazy값 update하는것 말고 또 신경써줘야하는 부분이 있나요..?

왜 틀린건지.ㅠㅠ

noeffserv   5달 전

appa님 choiking10님 답변 감사합니다. 

lazy propagation 으로 풀 때 저는 비트별로 segment tree를 이용했습니다..

그러니 데이터가 10만 이하라고 가정하면 사용되는 비트는 최대 17개니깐 segment tree가 17개가 있는거죠.

비트별로 lazy propagation 을 하는게 시간초과의 주범일까요? 아니면 이렇게 푸셨는지 궁금하네요

choiking10   5달 전

저는 세그먼트 트리 하나를 이용해서 한번에 범위갱신하는 식으로했는데... xor시 ^를 이용하구요. 홀수짝수 처리해주면 세그먼트 트리 하나만을 이용해서 풀수 있습니다. 

noeffserv   5달 전

맞았습니다. 감사합니다. ^^

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