ARC068-E : Snuke Line - 思考の墓場

　公式解説とは異なる解法を紹介。典型的な考え方を知っていると頭をあまり使わずに済むかも。

問題

考察と解法

　とりあえず $d$ を止めておく。区間 $[kd , (k+1)d$ ]と重なる名産品の区間の数が答えなわけだが、異なる $k$ の値について同じ区間が重なると数えるのが面倒である。しかし、区間 $[kd , (k+1)d$ ]に真に含まれる区間、つまり区間 $[l,r$ ]であって、 $kd \lt l \leq r \lt (k+1)d$ を満たすものは異なる $k$ の値について同じものはない。これは $d$ に対して条件を満たさないような区間であるから、これを数えることにしてみる。

　このような状況は典型的で、区間 $[l,r$ ]を2次元平面上の点 $(l,r)$ にプロットしてみよう。区間 $[kd , (k+1)d$ ]に対して $kd \lt l \leq r \lt (k+1)d$ を満たす区間に対応する点は、2次元平面上において、 $(kd,(k+1)d)$ の右下に当たる点に対応する。このような点の数は、平面走査によて数えることができる。つまり、 $x$ 座標( $l$ の値)の大きい順に走査し、 $y$ 座標( $r$ の値)はSegmentTreeなどで管理すればよい。
　 $d$ を固定した場合は解けたが、 $d=1,\cdots,M$ について解く必要がある。しかし、考えるべき区間の数は調和級数により $O(M\log M)$ であり、すべての $d$ について一度に平面走査を行えばよい。

実装

atcoder.jp

平面走査はやっていることの割に実装が軽い。