ARC 068 E - Snuke Line (700)

• 問題

問題概要

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

解法

各dについて dの倍数を含むような区間を数え上げていく.
愚直にやろうとすると [1,M] の d の倍数で, d を動かしていくと
ループの回数は M + M/2 + M/3 + .. M/M = O(MlogM) となり, 全てのN個の区間について数えれば全体で O(NMlogM) となる.

一方で, r_i - l_i >= d-1 となる区間は必ず倍数を含むので,
この区間については O(1) で求められまともに数えなくても良いことがわかる.
よって r_i - l_i でソートして r_i - l_i < d-1となる区間だけを見ていこうという発想が生まれる.

このような区間はdの倍数を高々1つしか含まない.
よってこの区間(今見ているdに対して, r_i - l_i < d-1 を満たすような区間)について,
cnt[ x ] := ( x と重なる区間は何個あるか ) としてやって,
i=d,2d,..kd の cnt[ x ] の和を数えればよい.
dの倍数を高々1つしか含まない性質から, cnt[ id ] と cnt[ jd ] (i!=j) が同じ区間を重複して数えていることはないからである.

また d を動かしていくと新しい区間を追加していく必要があるが, これは
cnt[ x ] ( l_i <= x <= r_i ) に +1 する操作になる.
これは FenwickTree(BIT)を使えば高速にできる.

FenwickTreeは1つ足す+区間和が求められるデータ構造だが,imos法のようにl_iに+1,r_i+1に-1すると,それまでの和がその数の値となる. 計算量は O(NlogN+logM*(M/1+M/2+..+M/M)) = O(NlogN + M(logM)² )

メモ

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

コード