문제 링크
- http://icpc.me/10641
사용 알고리즘
- PBS
- Segment Tree
풀이
쿼리가 하나만 있다면 파라메트릭 서치로 풀 수 있습니다. “답이 x 이하인가?” 라는 결정 문제만 잘 풀어주면 됩니다.
이런 결정 문제를 푸는 것은 삽입 쿼리를 삽입하는 값 기준으로 정렬한 뒤, 쿼리 $[a_i, b_i, v_i]$마다 세그먼트 트리의 구간 $[a_i, b_i]$에 1씩 더한 뒤 구간 $[x, y]$의 합이 $x$ 이상인지 확인해주면 됩니다.
PBS를 사용할 수 있는 형태이므로 쿼리가 여러 개 주어져도 PBS를 이용하면 빠르게 계산할 수 있습니다.
Dynamic Segment Tree를 만들어도 되고, 좌표 압축을 잘 해서 Lazy Propagation만 열심히 구현해줘도 됩니다.