1. 세그먼트 트리 구현 문제
2. 2차원 펜윅 트리 구현 문제
3. 스위치 (lazyprop)
4. 구간 합

구간들을 최댓값 순으로 정렬하는 문제

이때, 주어진 배열의 값은 모두 다르다.

(i번째 최댓값까지 같다면 i+1번째를 비교)

겹치는 부분을 제외하고 최댓값 세그에 쿼리를 날리는 cmp 함수를 만들어 std::sort를 사용

1. 직사각형 (화성 지도 세그)
2. 별 헤는 밤 : 온라인 2차원 구간 합 쿼리

(구간 범위 : $10^9$)

정해는 pst를 사용하는 방법이지만 2차원 다이나믹 세그를 짜서 맞음.

1. 내비게이션 : 두 점 사이 거리 (희소 배열)

짜기 귀찮아서 hld 템플릿 + 합 세그로 맞음.

1. 예약 시스템 (King Kog’s Reception)

문제 설명은 귀찮아서 생략

세그고, 구조체에 s~e가 다 끝나는 시간과 s~e의 총 소요 시간 합을 저장하면 두 노드를 합치는 게 가능해진다.

9, 10, 11 : 업솔빙 못함