Train Passenger Query (Hard)

解説

この問題はeasyとは違い、各クエリごとに特定の駅における乗客数の合計を求めなければなりません。よって、乗客数の増分を取ってその累積和を取る、という方法を用いる場合、各クエリごとに累積和を計算する必要があるので計算量は $O(QN)$ となり、実行時間制限に間に合いません。

この問題にACするためには、各駅ごとの乗客数の合計を記録する配列 $A$ に対して次のクエリを高速に行う必要があります。

• $A$ の $[s_j,t_j]$ に $c_j$ を加算する
• $A_{S_i}$ の値を求める

これらのクエリは遅延セグメントツリーを用いることで $1$ クエリ当たり $O(logN)$ で処理出来ます。時間計算量は $O((Q+\sum_{i=1}^{Q}M_i)\log N)$ より、(高速な言語であれば)実行時間制限に間に合います。

追記

Pythonのような低速な言語の場合、定数倍の重たい遅延セグメントツリーでは実行時間制限に間に合わない可能性があります。そこで、もう少し定数倍を軽くするために考察を入れてみます。 これを少し言い換えてみます。$A_i$ の前の要素からの増分$B_i = A_{i}-A_{i-1}(\text{ただし} A_0 = 0)$ となるような配列 $B$ を考えた際、$A$ に対するクエリは $B$ に対する次のクエリに等しいです。

• $B_{s_j}$ に $c_j$ を、$B_{t_j+1}$ に $-c_j$ を加算する
• $B_1+B_2+...+B_{S_i}$ の値を求める

これらのクエリはフェニックス木を用いることで$1$ クエリ当たり $O(logN)$ で処理出来ます。時間計算量は 遅延セグメントツリーを用いた場合と変わらず $O((Q+\sum_{i=1}^{Q}M_i)\log N)$ ですが、定数倍が軽くなります。

追追記

pythonで遅延セグメント木を使用した場合も、入力を高速化(input = sys.stdin.readline)することで十分間に合います。(590ms pypy使用)