Codeforces Round 719 (Div. 3)

Dashboard - Codeforces Round 719 (Div. 3) - Codeforces

 

F2

binary search를 이용하여 문제를 해결하면 된다. 다만 한번 날렸던 query는 어딘가에 저장(cache)하여 재활용을 해야하는 문제이다.

 

방법 1 - cache로 map 이용

이 방법에서는 query의 구간을 항상 위와 같은 형태(binary tree)가 되게 질의하고 질의의 결과를 cache에 저장한다.

위 그림에서 각각의 주황색 박스는 하나의 query를 의미한다. 예를들어 구간 [1, 4] query는 가장 왼쪽 가장 위쪽에 위치한 박스이다.
박스에 적혀있는 숫자는 query의 결과(구간에 속하는 1의 개수)를 의미한다.

 

 

 

 

 

 

방법 2 - cache로 BIT 이용