https://www.acmicpc.net/problem/10999
- 2월동안 187문제 풀기(지난달 누적 87개) (67/187)
- 드디어 풀어본 Lazy Propagation
- 이걸 진짜 외워서 적을 수 있나 의심이 든다.
- 일단 생성자에서 트리의 높이
h
를 구해놔야 한다. Count Leading Zero를 이용한다. 물론 그냥 while loop 돌아도 된다. - d 배열이 lazy 배열이다.
- d는 N 사이즈만 준다. leaf 들에는 lazy가 필요 없기 때문
- build(위로 올라가면서 업데이트), push(아래로 내려가면서 lazy 해소)
- range update
- 부분구간의 root에다가만 값을 써놓는다.
- root가 포함하는 leaf의 개수를 이용해서 값을 계산하고, lazy에도 값을 써둔다.
- 부분 구간의 root들을 집합 S라고 하면 이 S들의 부모들에다가도 값을 써줘야 한다.
- 양쪽 끝점에서 build를 이용해서 위로 올라가면 S들의 부모들을 모두 업데이트 할 수 있다. (그림을 그려보면 무조건 그렇다. 왜그런지 모르겟…)
- range query
- push를 통해서 아래로 내려가면서 lazy를 해소한다. lazy는 저 위에서 아래로 영향을 주기 때문에 반드시 하향해야 한다.
- 위에서랑 마찬가지로 양쪽 끝을 기준으로 내려오면 부분구간의 root들을 다 업데이트 할 수 있다.
1 |
|