ABC 106 D AtCoder Express 2
平面走査・ウェーブレットツリー
平面走査の考え方について
train の L, R と query の L, R の交差を考えることになるからしんどい。 R が交差しないようにすれば簡単。
R が交差するものは結果にカウントされないから、ある Q を考える時に R が交差しない T のみを考えれば十分で、上記の通り簡単になる。
→ T, Q 一緒に R に昇順に並べて前から処理していけば良い
解説では累積和を使っていた
交差があるから累積和が取りづらいように思われるがうまくいく
mat[l][r]: 左端が l 以下、右端が r 以下の集合と取ると、 mat[b][b] + mat[a-1][a-1] - mat[a-1][b] - mat[b][a-1] とすると、左端が a 以上 右端が b 以下として取ることができる。 l <= r であることが効いて、累積和の差が交差成分を取り除いてくれるような感覚
範囲だからと dp の持ち方を工夫する必要はなく、多分そうしても埋め方が難しい。シンプルに埋めてうまくいかないかを考える。
L 軸 R 軸の二次元平面で考えると非常にわかりやすい