冒頭からネタバレですが、やたらとdiffが低かった割には想定解法が遅延セグメント木だったので、おったまげた人が多かったようです。私もコンテスト中は遅延セグメント木使いましたが、E問題ごときでそんなん想定解のはずないだろって思い込んでいたので、たまげました。
自分が緑くらいのときは遅延セグメント木なんて知らなかったと思うので、遅延セグメント木以外で解く方法も必要でしょう。

そんなわけなので、あえて想定解と違う方法でも解いてみたので記事にします。

解法

平方分割ができそうな感触があるので、平方分割を検討してみる。

この問題が解けるには、区間加算と一点の値取得ができればよい。
遅延セグメント木を使えばこれを両方 $O(\log N)$ 程度の計算量でできるが、平方分割の場合は $O(\sqrt N)$ で捌くことを目指す。

具体的な方法としては、箱を $\sqrt N$ サイズのバケットに分割し、 $\sqrt N$ サイズの累積和をとれる配列を $A$ とは別にバケットごとに持つことにする。
区間加算は、imos法によって各バケットの加算したい区間の端に足し引きすることで行う。一点取得は、欲しい値のあるバケットの累積和を全部計算して、 $A$ に加算することで行う。

まず区間加算の計算量を考察する。バケットごとの区間加算は、区間の端を足し引きするだけなので、 $O(1)$ で行える。
区間加算で足さなければいけないバケットは $O(\sqrt N)$ 個あり、ハンパを処理するのに追加で $O(\sqrt N)$ 個加算が必要になりうる。
したがって、クエリごと $O(\sqrt N)$ 程度の計算量で処理することができる。

次に一点取得の計算量を考察するが、これはimos法によって押し付けられた累積和の計算と累積和配列のクリアだけなので、 $O(\sqrt N)$ で行えることが容易にわかる。

したがって、全体で $O(M\sqrt{N})$ の時間計算量ですべてのクエリを捌けることがわかる。

実装例は以下。
Submission #50189546 - KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）

36-42行目のところもループを回して $A$ に直接加算するようにしても、クエリごとの計算量は変わらず $O(\sqrt N)$ のはずだと思っているが、どうもここをサボるとTLEするらしい。
$N$ も $M$ もそれなりにデカいので $O(M\sqrt{N})$ が落ちても文句は言えないが、Rustくらい速い言語でも定数倍で落ちることがあるんだなあと思ったり思わなかったり…
なんかバグらせているだけかもしれないが、これ以上は追求しない。

あとがき

ちなみにコードが汚いのは平方分割書き慣れてないからです（というかまともに平方分割を使って問題解いたのは多分初めて）。
どうやったらもうちょいキレイに書けるんですかね？

（追記）一応補足しておくと、wrapping_add/wrapping_subの部分は普通にadd_assign/sub_assignで書いても良いし、その方が若干スッキリはする。が、ローカル環境でも常にrelease実行しなきゃいけなくて面倒なので、どっちがいいか問題はある。debug実行するとあらゆるところでパニックすることになる。
Submission #50192312 - KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）

競プロ備忘録

競プロerの備忘録

ABC340E - Mancala 2

解法

あとがき