### zeref_dragoneel's blog

By zeref_dragoneel, history, 3 years ago, Hi,

Let's say I have a set of lines, y = ax+b and three types of online queries:

1. Given a and b, insert the line.
2. Given a and b, delete the line (it is assured that the line exists)
3. Given x0, print the maximum possible value of y.

(a is distinct for all the lines, a & b are integers.)

number of lines <= 1e5.

number of queries <= 3e5.

So O(log n / log^2 n / sqrt n) should work, according to me.

Can anyone help me with this?  Comments (15)
 » 3 years ago, # | ← Rev. 2 →   If it's offline it's doable with LiChao segment tree in MlogMlog(Xmax * eps) about the same way you do dynamic connectivity: you support only insert operations on certain segments of activity (every segment is active from the moment it was inserted to the moment it got erased/the operations ended). Using LiChao segment trees you can also "take back" operations in logN (which can't be done with usual dynamic CHT).I'm not aware of any solution for the online version of this problem, although I have thought about that intensively.
•  » » Your can also use normal incremental CHT: If you store one data structure per recursion level and apply the updates to the one on the current level, the undo operation can be done by clearing the one on the current level. At the leaves, you query all data structures (at most ) and take the maximum. This takes time in total. If you presort all updates and queries by x-coordinate, the linear-time data structure for monotone coordinates and queries that uses a deque instead of a set can be used, this achieves time overall.For the online version, switch to a dual space where the problem is Insert the point (a, b). Delete the point (a, b). Query the extreme point the direction (x0, 1). To solve this, build a segment-tree (you might need one based on a BST for bigger coordinates) over the points sorted by x-coordinate where each node stores the upper convex hull in a persistent BST. When merging two nodes, we need to find the upper tangent of the convex hulls (as in the divide&conquer algorithm for convex hull), split the BSTs at the points where the tangents touch and join them. This can be done in by nesting two binary searches (one on the left and one on the right). Deletions and insertions are handled by the BST + recomputation along the insertion path by merging, they take each.To query, do a ternary search on the BST stored at the root. This will take time naively and can be sped up to if we each node stores it's successor in the persistent BST. The total memory consumption can be reduced to if each node reuses the same nodes for each merge done at it.The time for merging two upper hulls can be reduced to by a bunch of case-distinctions, see slides 20 — 30 here. This reduces the insertion and deletion time to .Finally, there's also an online solution with amortized time per insertion or deletion, see 'Dynamic Planar Convex Hull' by 'Riko Jacob', if you want to read 129 pages (I didn't).