主食は米

主に競プロ備忘録

ARC 068 E - Snuke Line

問題概要

N個の区間[l_i,r_i],自然数Mが与えられる.
1 <= d <= Mについて,dの倍数を含む区間はいくつあるかそれぞれ答えよ.
1 <= N <= 3*105, 1 <= M <=105

解法

まず,各dについてr_i - l_i >= d-1 となる区間は必ず倍数を含む.
よって r_i - l_i でソートして区間を見ていけば, r_i - l_i < d-1となる区間だけを見ていけば良いことになる.
逆に,このような区間はdの倍数を高々1つしか含まないから
このような区間があるたびに[l_i,r_i]に1を足して,d,2d,..kdの和を数えればよい.
これは FenwickTree(BIT)を使えば高速にできる.
FenwickTreeは1つ足す+区間和が求められるデータ構造だが,imos法のようにl_iに+1,r_i+1に-1すると,それまでの和がその数の値となる. 計算量は O(NlogN+logM*(M/1+M/2+..+M/M)) = O(NlogN+Mlog2M)

メモ

割と素直な解法だと思うが思いつかなかった.
区間に足しこんで数えようと思っていたら頭に浮かびそう.
倍数の全列挙がO(MlogM)なのも頭になかったかも.

コード