Li Chao Tree¶

Affine-DP optimization where previous states become lines and current states become point queries.

Microtopics¶

Source	Type
cp-algorithms Convex Hull Trick and Li Chao tree	`Reference`

Source	Type
CSES Monster Game I	`Practice`
CSES Monster Game II	`Practice`
Library Checker Line Add Get Min	`Practice`

Material	Type
CHT / Li Chao hot sheet	`quick reference`
Line Add Get Min note	`flagship note`
Monster Game II note	`flagship note`
Template Library exact starter route	`starter route`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Line Add Get Min	`Library Checker`	`Medium`	Line Container	Implementation; Verification	Line Evaluation; Lower Envelope Breakpoints	Point Queries	The most direct official verifier for the exact full-domain LineContainer route under the affine line-container family.
Monster Game I	`CSES`	`Hard`	Convex Hull Trick	Optimization; Monotone Structure	Affine DP Transform; Slope / Query Monotonicity	Affine DP; Monotone Hull; Line Container	The clean compare-point problem where the same affine DP family still admits a lighter monotone-hull route.
Monster Game II	`CSES`	`Hard`	Li Chao Tree	Optimization; Data-Structure-Heavy	Affine DP Transform; Line Evaluation	Affine DP; Line Container	The cleanest flagship for generic online min queries over lines with arbitrary insertion/query order.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Segment Add Get Min	`Library Checker`	`Hard`	Li Chao Tree, Segment Li Chao	Implementation; Verification	Segment Tree Thinking	Segment-Limited Lines; Advanced	The next-layer verifier once the basic full-domain Li Chao route is trusted and line activity ranges matter.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`LINEADDGETMIN`	Line Add Get Min	`primary`	`medium`	-	Note	Code
`MONSTERGAME2`	Monster Game II	`primary`	`hard`	li chao tree; affine dp; online line minimum	Note	Code

python3 scripts/generate_problem_catalog.py