14427번 - 수열과 쿼리 15
간단하지만 조금이나마 도움이 될까 싶어 올려봅니다
반례는 아래 첨부하였습니다.
힌트 : 각 입력마다, 사용하시는 자료구조가 어떻게 변하고 있는지 "출력"해보는 것을 추천드립니다.
풀이 접근 방법
1. 우선순위 큐 갱신
- 우선순위 큐를 갱신하는 방법을 생각해보기 (구현하기 나름. 여러 가지 방법이 있습니다)
2. 세그먼트 트리
- 전형적인 세그먼트 트리를 사용하면 됩니다. 세그먼트 트리를 모르신다면 공부하고 오시길 추천드립니다, BOJ BOOK에 매우 잘 설명되어 있습니다. https://book.acmicpc.net/ds/se...
잘 참고했습니다!!
헐 짱이에용. 덕분에풀었습니다!
저는 우선순위큐와 해시맵으로풀었는데 이거말고 우선순위큐를 갱신하는 다른방법이 뭐가있을까요?
@luke1546 님 도움이 되셨다니 다행입니다!
저는 lazy propagation(느린 갱신)을 이용했어요.
luke1546님의 제출 코드를 보니 저랑 비슷하게 푸신 것 같습니다.
아래는 제가 이 문제에 대해 정리해둔 포스팅 링크 첨부하겠습니다.
https://blog.naver.com/inpink_...
댓글을 작성하려면 로그인해야 합니다.
dnpdhd 3년 전 4
간단하지만 조금이나마 도움이 될까 싶어 올려봅니다
반례는 아래 첨부하였습니다.
힌트 : 각 입력마다, 사용하시는 자료구조가 어떻게 변하고 있는지 "출력"해보는 것을 추천드립니다.
풀이 접근 방법
1. 우선순위 큐 갱신
- 우선순위 큐를 갱신하는 방법을 생각해보기 (구현하기 나름. 여러 가지 방법이 있습니다)
2. 세그먼트 트리
- 전형적인 세그먼트 트리를 사용하면 됩니다. 세그먼트 트리를 모르신다면 공부하고 오시길 추천드립니다, BOJ BOOK에 매우 잘 설명되어 있습니다. https://book.acmicpc.net/ds/se...