Изменения

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