座標が \(D\) 以下の村の村人の総数が高速に分かれば、この問題に答えられます。なぜなら、その答えを \(f(D)\) とするとクエリの答えは \(f(R_i)-f(L_i-1)\) と表されるからです。

まず、\(x,D\) がそれぞれ \(0\) 以上 \(N\) 以下の場合を考えましょう。このときは、単純に累積和を求めておけば答えは \(\mathrm{O}(1)\) で求まります。

今回の問題の難しいところは、\(x,D\) (の絶対値) が大きいことです。これを解決するには、二分探索を用いればよいです。

座標が \(D\) 以下である最右の村は二分探索により求めることができます。これと累積和を組み合わせることで、\(f(D)\) を \(\mathrm{O}(\log N)\) で求めることが可能で、十分高速です。