Modular Range Counting

$B=450$이라 하자. 모든 $x\leq B$와 각 나머지에 대해 해당 나머지를 갖는 원소의 인덱스 목록을 만든다. 각 원소는 $B$개의 목록에 들어가므로 전처리 시간과 저장 공간은 $O(NB)$이다.

$x\leq B$인 쿼리는 해당 목록에서 이분 탐색 두 번으로 답한다. $x>B$이면 $A_i\leq B$이므로 나머지가 인 가능한 값은 최대 하나이다. 값별 인덱스 목록에서 같은 방식으로 센다.

쿼리당 시간 복잡도는 $O(\log N)$이다.

Solution written by GPT5