今日解いた競プロの問題。

ABC292-Ex: 遅延セグ木に(パフォ総和,コンテスト回数)の組を記録していたのを、Twitterで見かけたとおりパフォとBの差の総和を記録するように変更したらACした。本質的な変更してなくない？と思ったが前者は準同型性を満たしていないことに気付く。

当初の自分の回答では、遅延セグ木に以下のような構造を載せていた。

モノイド:

$(a,b)\cdot (c,d)=\left\{ \begin{array}{ll} (a,b) & (ad\geq cb) \\ (c,d) & (ad<cb) \end{array} \right.$

作用素:

$f_x((a,b))=(a+x, b)$

$f_x\circ f_y=f_{x+y}$

ちゃんと計算するとこれは$f_x((a,b)\cdot(c,d))=f_x((a,b))\cdot f_x((c,d))$を満たしていない。だから通らなかった訳だ。ちょっとでも変な構造を載せた場合は準同型性を満たしているか確認する！