square869120Contest 1 E - 散歩

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

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

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