문제 링크
- http://icpc.me/18437
사용 알고리즘
- Segment Tree
- Lazy Propagation
시간복잡도
- $O(N log N)$
풀이
먼저 오일러 투어 테크닉을 이용해 트리를 일자로 펴줍시다. 이렇게 하면 서브트리에 대한 쿼리를 구간에 대한 쿼리로 나타낼 수 있습니다.
1번 쿼리는 구간의 원소들을 모두 1로 세팅, 2번 쿼리는 모두 0으로 세팅하는 쿼리이고, 3번 쿼리는 구간합을 구하는 쿼리입니다.
Lazy Propagation을 이용해 쉽게 처리할 수 있습니다.