精進 ARC068E Snuke Line

何をしても時間がかかりそう...

と悩んでいたが解説見てー

あーなるほどってなった

わかってたこと

r - l + 1 > d を満たす区間は必ず１回以上通る

それ以外は通らない、または１回だけ通る(つまり分からない)

わからなかったこと

倍数の計算量の抑え方

方針

・dはループで1~mまで計算する

・r - l + 1 <= d を満たす区間[l,r]に1加算する

このようにすることで、

dの倍数全てについて総和を取ることで

通るか通らないか分からない区間について調べることができる

つまりdについて

N - (r - l + 1 <= d を満たす区間  つまり通るかわからない区間)
  + (駅[i]における分からない区間の名産品の種類の数 | i は d の倍数)

とできるね

あとはBITを使うだけ

とは言いつつBITとimos法を合体させてるの面白くないですか

僕は面白いなーと思った