We consider an offline technique and answer queries in order of ascending \(C_i\).

Consider an array \(S\) of length \(2N\), starting with all zeros. For each segment \((A_i, B_i)\), we add \(1\) to \(S_{A_i}\), and subtract \(1\) from \(S_{B_i}\). Note we may now answer all queries with \(C_ j= 1\), because the subarray sum of \(S_{C_j ... D_j}\) will reflect the number of \((A_i, B_i)\) segments that cross the \((C_j, D_j)\) segment. [Any \((A_i, B_i)\) segment that’s fully contained or not contained in the \((C_j, D_j)\) segment would contribute \(0\) to the sum, while any \((A_i, B_i)\) segment that has \(A_i\) contained but not \(B_i\) would contribute \(1\) to the sum.]

Now we want to transition array \(S\) to be able to answer queries from \(C_j = x\) to \(C_j = x + 2\). This means that for each \((A_i, B_i)\) segment with \(A_i = x + 1\), we want to swap the “polarity” of the endpoint values, i.e. we subtract \(2\) from \(S_{A_i}\) and add \(2\) to \(S_{B_i}\), so that the contributions of the endpoints are now reversed. This way, when it’s time to answer a query, \((A_i, B_i)\) segments that has \(B_i\) contained in \((C_j, D_j)\) but not \(A_i\) would also correctly contribute \(1\) to the subarray sum of \(S_{C_j ... D_j}\).

We could use either Fenwick tree or segment tree to be able to update values and query subarray sums quickly, which means this solution will run in \(O(N + (M + Q) \log N)\) time. Note that this solution does not use the constraint that none of the \((A_i, B_i)\) segments share a point.