Всем привет.

В этом посте я хотел бы предложить несколько задач на CHT.

Ниже приведены статьи про CHT, дерево Ли Шао.

https://codeforces.me/blog/entry/63823

https://neerc.ifmo.ru/wiki/index.php?title=Convex_hull_trick

https://cp-algorithms.com/geometry/convex_hull_trick.html

https://wiki.algocode.ru/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_Li_Chao

Задачи, которые можно решить с использованием CHT с стеком

1083E - The Fair Nut and Rectangles

311B - Cats Transport

Задачи ниже вы можете решить с использованием дерева Ли Шао или димнамического CHT

1303G - Sum of Prefix Sums

1175G - Yet Another Partiton Problem

932F - Escape Through Leaf

792F - Mages and Monsters

631E - Product Sum