AtCoder Express 2 - abc 106 d - tac

#2次元累積和 #圧縮

解法

列車 i は $[L_{i}, R_{i}$ ] を走っている
2次元座標にプロットすると, 1 点で表せる
L = $L_{i}$ , R = $R_{i}$ のところ

各 query を考える
区間 $[p_{i}, q_{i}$ ] に収まっている列車の本数
L = $p_{i}$ に対し, R = $p_{i}, p_{i + 1}, ..., q_{i}$
L = $p_{i + 1}$ に対し, R = $p_{i + 1}, ..., q_{i}$
...
L = $q_{i}$ に対し, R = $q_{i}$

ここで,
L = $p_{i}$ に対し, R = $p_{i}, p_{i + 1}, ..., q_{i}$
L = $p_{i + 1}$ に対し, R = $p_{i}, p_{i + 1}, ..., q_{i}$
...
L = $q_{i}$ に対し, R = $p_{i}, p_{i + 1}, ..., q_{i}$
としてもよい

なぜなら, L > R のとき列車はなく, そこを累積和に入れても何も足されないから

コード
https://atcoder.jp/contests/abc106/submissions/9342264