AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）

　Fまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） Fまで
C A[i]*（iより右の和）を足し合わせる
D BFS
E 一番右にあるAより左にあるBの個数で場合分け
F 線分の間を+1すると、クエリは階段を何段上り下りするかになる。実装はセグ木で。
G Mo's algorithmと思ったが分からず。

— titia (@titia_til) May 10, 2025

G - Range Shuffle Query

　ACできなかったのは仕方ないが、Mo＋セグ木の解法は自力で思いつかなくてはいけなかった。

　平方分割するとセグ木を使うより計算量が良くなることは知らなかった。頭に入れておきたい。

　ところで、Moを書くときは、区間を広げた後、縮めていくように書くべきだということも知らなかった。今回、PyPyでTLEを取ることができず、ChatGPTにRUSTに直してもらったのだが、それが原因で配列外参照が起こってしまった。原因が分からず大分苦労した。