\(D\) が固定されていると仮定します。

任意の要素が \(0\) で初期化された長さ \(2N\) の数列 \(V\) に対して、以下の操作を \(i = 1, 2, \dots , M\) の順に行います。

• \(B_{i} < D\) ならば、\(V[A_{i}]\) に \(-1\) を加算し、\(V[B_{i}]\) に \(1\) を加算する。
• \(D < B_{i}\) ならば、\(V[A_{i}]\) に \(1\) を加算する。

すると、\(k\) 番目のクエリの答えは \(V[C_{k}] + V[C_{k} + 1] + \cdots + V[D]\) となります。

\(D\) が固定されていなくても、\(D_{k}\) の昇順にクエリを見て、適切に \(V\) を変更することで、\(1\) 点更新・区間和の問題に帰着できます。

よって、BIT や segment tree を用いて十分高速に解くことができます。

c++ 実装例