Всем привет.

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

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

https://codeforces.net/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 - Орехус и прямоугольники

311B - Транспортировка кошек

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

1303G - Сумма префиксных сумм

1175G - Очередная задача на разбиения

932F - Сбежать через лист

792F - Маги и монстры

631E - Мультипликативная сумма