BOJ 13982 Shopping

먼저 중요한 관찰을 하나 해야 합니다. $x$와 $a_i$가 주어졌을 때, $x \bmod a_i$는 $x$ 값을 유지하거나 아니면 $\frac{x}{2}$ 이하로 감소합니다. 이것의 이유는 다음과 같습니다.

• $x < a_i$이면 값이 유지됩니다.
• $a_i \le x < 2 a_i$이면 값은 $x - a_i$로 바뀌는데, $x < 2 a_i$와 $x - a_i < \frac{x}{2}$는 동치입니다.
• $k a_i \le x < (k+1) a_i$ ($k \ge 2$)이면, $x \bmod a_i < a_i < 2 a_i \le x$가 됩니다.

따라서, 각 쿼리에 대해 $x$가 감소하는 $a_i$들만을 콕콕 집어서 계산해주게 되면 쿼리당 최악 $\log 10^{18}$번의 나눗셈 연산만을 수행하여 시간 내에 돌 것이라고 예상할 수 있습니다.

이제 $[l, r]$에서 $x$ 이하인 수 중 가장 왼쪽에 있는 수를 빠르게 찾을 수 있으면 이 문제를 해결할 수 있습니다.

한 가지 방법은 sparse table을 쓰는 것입니다.

먼저, 수열의 각 수에 대해 자신보다 작으면서 자신의 오른쪽에 있는 수 중에서 가장 왼쪽에 있는 것의 인덱스를 구합니다. 이 함수를 $f(i)$라고 합시다. 이는 스택으로 $\mathcal{O} (n)$에 구할 수 있습니다. 이제 $f(i)$를 $2^k$번 중첩한 sparse table을 계산해 둡니다.

이제 쿼리의 $(x, l, r)$이 주어졌을 때, 인덱스가 $l$ 이상이면서 $x$ 이하인 $a_i$를 sparse table을 이용한 이분 탐색으로 구할 수 있습니다. 그러한 인덱스가 없거나 $r$보다 오른쪽이면 종료하고, 그렇지 않다면 $x$를 $x \bmod a_i$로 바꾼 다음 $l$을 $f(i)$로 옮겨서 계속 진행합니다.