Изменения

Будем хранить 2 массива : <math>front[]</math> - <math>x</math>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <math>x</math> <tex>\in</tex> <math>[front[i]; front[i + 1])</math> ) и <math>st[]</math> - номера деревьев, соответствующих прямым (т.е. <math>i</math>-я прямая множества, где <math>i</math> <tex>\in</tex> <math>[1; sz]</math> соответствует дереву номер <math>sz[i]</math>). Также воспользуемся тем, что <math>x[i] = a[i]</math> возрастают (по условию задачи), а значит мы можем искать первое такое <math>j</math>, что <math>x[i] >= front[j]</math> не бинарным поиском, а методом 2х двух указателей за <math>O(n)</math> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые <math>x[i]</math>, а значит если <math>k</math>-я прямая пересекается с <math>k+1</math>-й в точке <math>z +</math> <tex>\alpha</tex> (z-целое, <tex>\alpha</tex> <tex>\in</tex> <math>[0;1)</math>), то мы будем подставлять в их уравнения <math>z</math> или <math>z + 1</math>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <math>x = z+1</math>