hellogaon

14577번: 일기 예보 - 구간트리 (세그먼트 트리) kks227님 블로그의 오프라인 쿼리를 읽고 인상 깊어 작성하게 되었다.이 문제에서는 4개의 쿼리가 있다.1. 하나의 값에 X를 더한다.2. 하나의 값에 Y를 뺀다.3. 값이 L ~ R 사이인 원소의 개수를 구한다.4. K번째로 큰 값을 구한다.이러한 쿼리들을 10^5개를 처리해주면 되는 문제이다. 1번과 2번은 구간트리에서 많이 접해본 적이 있다.어떤 idx에 대하여 X를 더하는, Y를 더하는 과정은 O(lgN)에 구할 수 있다. 3번 쿼리는 값이 L ~ R 사이인 원소들의 개수를 구하는 쿼리이다.이 쿼리를 어떻게 처리해야할까?나라들의 현재 값이 들어있는 배열을 A라 할 때 A = {1, 2, 10, 2, 4} 가 된다고 하자.구간트리에 이 값이 ..