BUS (hard)

解説

$B_i \leq l_j < r_j \leq E_i$ を満たすような $j$ $(1 \leq j \leq M)$ の個数を求めるには、始発のバス停から数えて $l$ 番目のバス停で乗車し、 $r$ 番目のバス停で降車するような客の人数を $a_{(l,r)}$ として、$a_{(p,q)}$ $(B_i \leq p < q \leq E_i)$ の和を求めれば良いです。

しかしこの和を愚直に求めようとすると、最悪の場合ほぼ全ての $a_{(p,q)}$ を求める必要があるため、1クエリ当たり $O(N^2)$ となり、クエリ処理に $O(N^2Q)$ かかってしまい実行時間制限に間に合いません。そこで、$a_{(p,q)}$ $(B_i \leq p < q \leq E_i)$ の和を二次元累積和を用いて高速に求められるようにすると、各クエリを定数時間で処理できるため、クエリ処理にかかる計算量を $O(Q)$ に減らすことが出来ます。二次元累積和の前処理には $O(N^2)$ かかるため、全体の時間計算量は $O(N^2+M+Q)$ となり、これは実行時間制限に間に合います。