各クエリは2次元平面上で以下の2つの矩形内の点の個数を数える問題と考えられます。

• \(1\leq a <c\) かつ \(c\leq b<d\)

• \(c\leq a <d\) かつ \(d\leq b<2N+1\)

これはRectangle Sumと呼ばれる問題で、Wavelet Matrixなどを用いて高速に解くことができます。計算量は\(O((N+Q)\log N)\)で十分高速です。