This editorial describes the intended solution. Other methods including square root decompoistion likely perform better.

We use a persistent dynamic (allocate nodes as we go) Li Chao Tree to support insertion of lines, queries at an x-coordinate, and rollbacks.

Next, we maintain a segment tree whose leaves represent the versions of the 2D-plane in increasing order of time. Each line exists as a single contiguous range in time. We add each line to the ~O( \log N ) ~ nodes in the segment tree corresponding to the time it exists. We add each output query to the corresponding leaf of the segment tree.

Next, we perform an Euler Tour of the tree, adding the lines to the Li Chao Tree when entering the node and rolling back the lines when exiting the node. At the leaf of each node, the lines in the Li Chao Tree will correspond to the lines in the 2D-plane at the point in time. We answer the queries stored in the leaf and make sure to print out the queries in the order that they are given.

Additional Reading:

• Li Chao Tree
• Additional segment tree technique