ark4rk.hatenablog.comこれを事前に読んで欲しいです。 分割統治法の方針でセグ木に乗せられます これにより、 点更新 [l,r)間の連続部分列における総和の最大値を求める が出来ます からなるベクトルを考えると、これがモノイドになっています。試しにベク…

拡大係数行列を考える。 この時、の時のみ解が存在する事が知られている。 転置行列についてもrankは同じであるため、で計算が出来る。 からでが求められる事から転置行列においては2倍の定数倍高速化も可能である。