sgc109   3달 전

http://codeforces.com/contest/580/problem/E

이 문제를 풀고있는데 문자열의 구간들의 해시값으로 세그트리를 만들었는데

트리의 노드를 초기화해주는 함수와 query 함수는 O(lgn) 으로 구현했는데

특정 구간의 문자열을 모두 특정 문자로 바꾸어 세그트리를 update 해야 하는 부분은 아무리 생각해봐도 O(n) 로 밖에 구현하지못하겠습니다..

n 이 최대 100000인데 쿼리를 최대 100000번 날려서 모든 연산을 O(lgn) 으로 만들어야 AC 를 받을 수 있을 것같은데

세그트리의 특정 구간을 같은 수로 update 하는것이 O(lgn) 으로 가능한가요?

lazy propagation 쓰시면되지않나요?

sgc109   3달 전

smu201111192 아 그런게 있었군요.. 검색해보겠습니다 감사합니다!

네 파이팅요

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