ARC068-E : Snuke Line
公式解説とは異なる解法を紹介。典型的な考え方を知っていると頭をあまり使わずに済むかも。
問題
考察と解法
とりあえずを止めておく。区間]と重なる名産品の区間の数が答えなわけだが、異なるの値について同じ区間が重なると数えるのが面倒である。しかし、区間]に真に含まれる区間、つまり区間]であって、を満たすものは異なるの値について同じものはない。これはに対して条件を満たさないような区間であるから、これを数えることにしてみる。
このような状況は典型的で、区間]を2次元平面上の点にプロットしてみよう。区間]に対してを満たす区間に対応する点は、2次元平面上において、の右下に当たる点に対応する。このような点の数は、平面走査によて数えることができる。つまり、座標(の値)の大きい順に走査し、座標(の値)はSegmentTreeなどで管理すればよい。
を固定した場合は解けたが、について解く必要がある。しかし、考えるべき区間の数は調和級数によりであり、すべてのについて一度に平面走査を行えばよい。
実装
平面走査はやっていることの割に実装が軽い。