7K12 blog

猫でも分かるアルゴリズム解説

square869120Contest 1 E - 散歩

f:id:tkr987:20200802163821p:plain

f:id:tkr987:20200802163830p:plain

https://atcoder.jp/contests/s8pc-1/submissions/15582396

  • 半開区間はデータの境界を表す

f:id:tkr987:20200802173417p:plain
制約から1個のクエリを O(N)未満で処理する必要がある。街Aから街Bへ移動するとき移動距離は半開区間[A, B)で表される。したがって、半開区間そのまま累積和で加算処理していけば答えが得られる。累乗を繰り返し二乗法で高速化してメモ化し、modを取るのを忘れないよう注意する。計算量は O(Q)になる。