tw99534   2달 전

계속 시간 초과가 나네요ㅜㅜ 도대체 어디 부분이 문제일까요....??

직접 업데이트와 계산을 쿼리마다 처리하게 되면 연산량이 500000*500000으로 제한시간 내에 수행될 수 없습니다.

풀이 방법은 많을 수 있겠지만,

저는 DFS를 이용해 트리를 펼치고, 펼쳐 놓은 트리를 리프로 하는 세그먼트 트리를 만들어 lazy propagation을 이용해 풀었습니다.

간신히 1초 안쪽으로 도네요.

해당 알고리즘에 관심이 있으시다면 segment tree, lazy propagation 등의 키워드로 검색해보세요.

tw99534   1달 전

아 그렇군요 생각보다 복잡해 지네요...ㅜㅜ 세그먼트 트리를 공부해봐야 겠습니다. 조언 정말 감사드립니다!

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