ABC 401-500/ABC425C - Rotate and Sum Query - 競技プログラミング用 知識集積所

---

問題

ABC425C

必要知識

B以下レベルの内容は省略

• 累積和

考え方

愚直にやって簡単そうに見えるが、それでは計算量が多すぎてTLEする。

まず第1の問題が、クエリ1に時間がかかりすぎる問題。
先頭の除去が素早くできるdeque※を用いたとしても、cの値が大きければそのクエリの処理にc回の処理が必要。
cがほぼNに近いクエリをQ回のほとんどに入れられると、計算回数目安の1億回では全く足りない。

これに対しては、データの方ではなくスタート位置を更新することで対応する方法がある。
例えば、クエリ1で値2が来たとしたら、「今後は位置xと言われたらx+2番目のことだと思う」ということにしておく。
そこに続けてクエリ1で値3が来たら、「今後は位置xと言われたらx+5番目のことだと思う」ということにしておく。
つまり、クエリ1では底上げの値にcを加えるという処理で済むようにすれば、cの値が大きくても処理は素早く終えられる。

しかし、この対策のせいで第2の問題が発生する。
全体の長さが5のときに、「1 3」が来た後に「2 1 4」が来るとする。
すると、これは「5番目から7番目の和を答える」になるが、6番目や7番目など存在しない。
これは実際には後ろに移動してきた1番目と2番目のことである。
ループしてまたスタートから和を取るということを考えてもよいが、これにはもっと簡単な対応がある。
それは、Aの後ろにAをもう1セット用意して、長さ2Nにしてしまう方法。
こうすれば、6番目や7番目が本当に存在するデータになるので、少しくらいはみ出ても困らない。
では、クエリ1が大量に来て「100番目から102番目の和になったら？」に対しては、クエリ1の更新時に、底上げ分がN以上だったらN引いておく（またはNで割った余りにする）方法でよい。
LやRはN以下、底上げもN未満なので、見たい番号は必ず2N未満になる。

最後に、区間が長いと和を取るのが大変だという第3の問題。
これは累積和の通常の使い方でそのまま対応できる。

以上をきちんと実装すればよい。

解答例

解答例

注意点

和はint型には収まらない。

必要なところにはlong long型を使うこと。

別解