If we can count the number of villagers with coordinates less than or equal to \(D\), then the problem can be solved, because the answer for a query can be found as \(f(R_i)-f(L_i-1)\), where \(f(D)\) to that subproblem.

First, let us assume that \(x\) and \(D\) are between \(0\) and \(N\). In this case, we can simply precalculate the cumulative sums to find the answer in \(\mathrm{O}(1)\) time.

But the difficulty in the original problem lies in the large (absolute value of) \(x\) and \(D\). To overcome the issue, we may use binary search.

The rightmost village with coordinate \(D\) or less can be found with binary search. Together with the cumulative sums, one can find \(f(D)\) in \(\mathrm{O}(\log N)\) time, which is fast enough.