BUS (easy)

解説

各バス停における乗客の人数を求める際にまず思いつく解法として、各乗客について、$l_i$ 番目から $r_i -1$ 番目までのバス停のカウントを+1していくというものが考えられますが、この解法での時間計算量は最大で $O(NM)$ となり実行時間制限に間に合いません。

では、どうすれば良いのでしょうか。ここでは、imos法という累積和の応用アルゴリズムを使うことで計算量の削減を図ります。まず、各バス停における乗客の増減を管理する配列 $S$ を用意します。ここで、$M$ 人の乗客の増減は、各乗客について $l_i$ 番目のバス停で+1、$r_i$ 番目のバス停で-1されます。つまり、0で初期化された配列$S$に、$l_i$ 番目を+1、$r_i$ 番目を-1する操作を行うことによって全てのバス停における乗客の増減を記録することができます。この増減を配列の初めから順番に受け取り、その都度乗客の人数を計算することで時間計算量を $O(N+M)$ まで削減することができます。 クエリ処理は $O(Q)$ で行えるため、全体の時間計算量は $O(N+M+Q)$ となり実行時間制限に間に合います。