精進 ARC068E Snuke Line
何をしても時間がかかりそう...
と悩んでいたが解説見てー
あーなるほどってなった
わかってたこと
r - l + 1 > d を満たす区間は必ず1回以上通る
それ以外は通らない、または1回だけ通る(つまり分からない)
わからなかったこと
倍数の計算量の抑え方
方針
・dはループで1~mまで計算する
・r - l + 1 <= d を満たす区間[l,r]に1加算する
このようにすることで、
dの倍数全てについて総和を取ることで
通るか通らないか分からない区間について調べることができる
つまりdについて
N - (r - l + 1 <= d を満たす区間 つまり通るかわからない区間)
+ (駅[i]における分からない区間の名産品の種類の数 | i は d の倍数)
とできるね
あとはBITを使うだけ
とは言いつつBITとimos法を合体させてるの面白くないですか
僕は面白いなーと思った