CPLib.Monoid
Defined in cp-library@0.15.1
セグメント木でよく使うモノイドと作用を提供するモジュール。
CPLib.SegtreeとCPLib.LSegtreeは、モノイドの型(Monoidトレイトを実装した型)と作用の型(Actionトレイトを実装した型)を要求します。
自作の型にMonoidトレイトやActionトレイトを実装して使うこともできます(書き方の例はCPLib.SegtreeとCPLib.LSegtreeのモジュールの説明にあります)。
このモジュールは、競技プログラミングでよく使うモノイドと作用の型を用意し、MonoidトレイトとActionトレイトを実装しています。
モノイドはSum e、Product e、Min e、Max e、WeightedSum eです。
eはI64やF64などの要素の型で、それぞれのモノイドが必要とする演算のトレイト(Add、Mul、LessThanなど)と単位元のトレイト(Zero、One、Inf、NegInfなど)を実装している必要があります。
モノイドの値はフィールドvに入れます(WeightedSumはvとwの2つ)。
たとえばMax I64の値はMax { v : 3 }で作り、x.@vで取り出します。
WeightedSum eはe型の値2つ(フィールドvとw)の組で、op((v1, w1), (v2, w2)) = (v1 + v2, w1 + w2)と定義されています。
典型的には、LSegtreeで和のモノイドを扱うときに使います。
このときwはノードが受け持つ区間の長さ(葉では1)を表し、区間への作用を計算するのに使われます。
作用はRangeAdd m e、RangeMul m e、RangeAssign m e、RangeAffine m eです。
mは作用を受けるモノイドの型コンストラクタ(Max eではなくMax)で、eはモノイドの要素の型です。
利用できるモノイドと作用の組み合わせと、作用の内容は次のとおりです。
| 作用 | Sum { v } |
Min / Max { v } |
WeightedSum { v, w } |
|---|---|---|---|
RangeAdd { a } |
なし | v + a |
(v + w a, w) |
RangeMul { a } |
a v |
a v(a >= 0) |
(a v, w) |
RangeAssign { a } |
なし | a |
(w a, w) |
RangeAffine { a, b } |
なし | a v + b(a >= 0) |
(a v + b w, w) |
表のセルは、作用を受けた後の値です(WeightedSumは(v, w)の組)。
RangeAssignのフィールドaはOption eで、some(c)ならcを代入し、none()なら何もしません。
モノイドや作用の計算には、オーバーフローを防ぐ仕組みはありません。
特に、Min / Maxを使うセグメント木をcreateで作ると、すべての要素がinf(Maxではneg_inf)で初期化されます。この状態では、作用によって整数はオーバーフローしやすく、浮動小数は0を掛けるとNaNになることに注意してください。
これらのモノイドや作用でセグメント木を作るときは、次のように型注釈でモノイドと作用を指定します。
import CPLib.LSegtree;
import CPLib.Monoid;
import CPLib.Segtree;
let segtree = Segtree::build([1, 2, 3].map(|v| Max { v })) : Segtree (Max I64);
let lsegtree = LSegtree::build([1, 2, 3].map(|v| Max { v })) : LSegtree (Max I64) (RangeAdd Max I64);
let lsegtree = lsegtree.act_range(0, 2, RangeAdd { a : 10 }); // [11, 12, 3]
assert_eq(|_|"", lsegtree.fold(1, 3).@v, 12);;
assert_eq(|_|"", segtree.fold(0, 2).@v, 2)
Values
namespace CPLib.Monoid::RangeAssign
make
Type: e -> CPLib.Monoid::RangeAssign m e
値cを代入する作用を作る
Parameters
c: 代入する値
namespace CPLib.Monoid::WeightedSum
make_single
Type: [e : Std::One] e -> CPLib.Monoid::WeightedSum e
重みが1の値を作る
Parameters
v: 要素の値
Types and aliases
namespace CPLib.Monoid
Max
Defined as: type Max e = unbox struct { ...fields... }
最大値のモノイド
単位元はneg_infです。
field v
Type: e
Min
Defined as: type Min e = unbox struct { ...fields... }
最小値のモノイド
単位元はinfです。
field v
Type: e
Product
Defined as: type Product e = unbox struct { ...fields... }
積のモノイド
field v
Type: e
RangeAdd
Defined as: type [m : *->*] RangeAdd m e = unbox struct { ...fields... }
区間加算の作用
型引数mは作用を受けるモノイドの型コンストラクタ(Min、Max、WeightedSum)、型引数eは要素の型です。
field a
Type: e
RangeAffine
Defined as: type [m : *->*] RangeAffine m e = unbox struct { ...fields... }
アフィン変換x -> a * x + bの作用
型引数mは作用を受けるモノイドの型コンストラクタ(Min、Max、WeightedSum)、型引数eは要素の型です。
Min / Maxに作用させるときは、フィールドaを0以上にしてください。負だと作用の定義を満たしません。
field a
Type: e
field b
Type: e
RangeAssign
Defined as: type [m : *->*] RangeAssign m e = unbox struct { ...fields... }
区間代入の作用
型引数mは作用を受けるモノイドの型コンストラクタ(Min、Max、WeightedSum)、型引数eは要素の型です。
フィールドaがsome(c)のときはcを代入し、none()のときは何もしません。RangeAssign::make(c)はRangeAssign { a : some(c) }を作ります。
field a
Type: Std::Option e
RangeMul
Defined as: type [m : *->*] RangeMul m e = unbox struct { ...fields... }
区間乗算の作用
型引数mは作用を受けるモノイドの型コンストラクタ(Sum、Min、Max、WeightedSum)、型引数eは要素の型です。
Min / Maxに作用させるときは、フィールドaを0以上にしてください。負だと作用の定義を満たしません。
field a
Type: e
Sum
Defined as: type Sum e = unbox struct { ...fields... }
和のモノイド
LSegtreeで区間に加算・代入・アフィン変換を作用させる和にはWeightedSumを使います(区間乗算はSumにも作用します)。
field v
Type: e
WeightedSum
Defined as: type WeightedSum e = unbox struct { ...fields... }
重みつきの和のモノイド
葉をmake_singleで作るとwは1になり、ノードのwはそのノードが受け持つ区間の長さになります。
木はmake_singleで作った葉からbuildで作るか、createの後にsetで葉を入れてください。createの要素はwが0で、作用を受けても変わりません。
field v
Type: e
値と重みの積の和
field w
Type: e
重みの和