NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）
F問題 Operations on a Matrix
状態が多くて脳が破壊された。
だいたいの情報は両端キューで管理して適宜pop_front()するとすこし楽になる。
まずタイプ1(l,r,x)のクエリによってj列目に足された合計はすぐ求まる。 これを「累積和」と呼ぶことにする(遅延セグ木、FwnwickTreeでimos法)。
タイプ2(i,x)が問題で、タイプ3が来たときに、これより前で最新のタイプ2の更新値だけが影響する。
タイプ3(i,j)が来た時に、「i行目のタイプ2での最後の更新値+現在の累積和[j]-最後のタイプ2が来た時点での累積和[j]」を計算できれば答えが求まる。
しかし愚直にやるとO(MQ)のメモリが必要になり無理。
うまく必要な情報だけを管理したい。
具体的にどうするか。
- タイプ2(i,x)が来た時
i行目で次のタイプ2のクエリがくるまでの間にあるi行目のタイプ3(i,j)について、両端キュー[i]に現在の累積和[j]を追加する。
i行目の最終更新値[i]=xに更新する。
（事前にi行ごとにタイプ2がくるタイミングを計算しておく（両端キューにいれておく））
（事前にi行ごとにタイプ3を両端キューにいれておく）
（（とくにi行目で最初のクエリ2の時）現在のタイプ2が来るまでの間に存在するタイプ3に対応する値を追加しないように注意）
- タイプ3(i,j)がきたとき
a = 現在の累積和[j]
b= 両端キュー[i].pop_front() または 空なら0
c = 最終更新値[i]
として が求める答え。
（両端キュー[i].pop_front()がi行目で最後にタイプ2が来た時点での、現在のタイプ3に対応するj列目の累積
和になる）
両端キューにいれた値は適宜捨てていくことで、計算量を抑えることができる。
