문제 요약
- 책이 있음. 가격은 1000~1000000원
- 한 페이지에 가격이 두 배 이상 차이나는 책을 진열할 수 없음
- 쿼리가 주어짐
- 책을 추가, 책을 삭제
- 책을 진열하기 위한 최소 페이지 출력
접근법
- 최소 가격을 구하고 -> 2배 가격을 구하고(더 커도 됨) -> 그 다음 2배 가격을 구하고...
- 최소값 = 10^3 = 2^10
- 최대값 = 10^6 = 10^3^2 = 2^20
- 2배씩 해도 최대 10번 정도 반복함
- 그런데 특정한 값을 어떻게 찾음? -> 값이 업데이트 되는 상황에서 lower_bound
- 여러가지 방법이 있겠지만 최대값을 갖는 인덱스 트리로 접근해봄
- 값이 업데이트 될 때마다 최대값도 갱신해줌
- 값 별 카운팅 변수는 별도로 가지고 있음(중복 업데이트가 가능)
- 구간의 최대값을 알고 있음
- 찾으려는 값이 왼쪽에 속하면 왼쪽으로, 오른쪽에 속하면 오른쪽으로 탐색
- 그런데 공식 editorial에 따르면 이런 방식의 인덱스트리고 가능함
- 구간의 개수를 갖고 있는 인덱스 트리 구성
- (최소값) ~ (2 * 최소값 - 1) 까지의 개수를 구함 -> K
- K + 1 번째 수를 구함 -> 2배 큰 값
- tree map set + lower bound로도 풀 수 있다고 함
newbieski