Convex hull trick

Правка ru5, от topovik, 2020-03-13 14:32:24

Всем привет.

В этом посте я хотел бы предложить несколько задач на 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 - Мультипликативная сумма

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский topovik 2020-03-13 14:32:24 398
ru4 Русский topovik 2020-02-27 14:20:35 36 Мелкая правка: 'blem:792F]' -> 'blem:792F]\n\n[problem:311B]\n\n[problem:631E]'
ru3 Русский topovik 2020-02-27 10:52:10 2 Мелкая правка: 'ry/63823\nhttps://' -> 'ry/63823\n\nhttps://'
ru2 Русский topovik 2020-02-27 10:51:38 215
ru1 Русский topovik 2020-02-27 10:42:35 567 Первая редакция (опубликовано)