P4097 [Template] Li Chao Segment Tree / [HEOI2013] Segment

Maintain two operations in the 2D Cartesian coordinate system: 1. Insert a line segment into the plane. The index of the i-th inserted segment is $i$. 2. Given a number $k$, query among all segments that intersect the line $x = k$, and return the index of the segment whose intersection point has the largest $y$-coordinate.

This problem enforces online input. The first line contains an integer $n$, the number of operations. Then $n$ lines follow. On each line there are several integers separated by spaces. On the $(i + 1)$-th line, the first integer is $op$, indicating the type of the $i$-th operation. - If $op = 0$, then it is followed by an integer $k$. This operation queries among all segments that intersect the line $x = (k + lastans - 1) \bmod 39989 + 1$, and returns the index of the segment whose intersection point has the largest $y$-coordinate. - If $op = 1$, then it is followed by four integers $x_0, y_0, x_1, y_1$. Define $x_i' = (x_i + lastans - 1) \bmod 39989 + 1$, $y_i' = (y_i + lastans - 1) \bmod 10^9 + 1$. This operation inserts a segment with endpoints $(x_0', y_0')$ and $(x_1', y_1')$. Here $lastans$ is the answer to the previous query. Initially, $lastans = 0$.

For each query, output one line containing a single integer: the index of the segment whose intersection point has the largest $y$-coordinate. If no segment intersects the query line, output $0$. If multiple segments have the same maximum intersection $y$-coordinate, output the smallest index among them, and $lastans$ should also be updated to this smallest index.

### Explanation for Sample $1$ For the first operation, after decoding it becomes `1 8 5 10 8`. For the second operation, after decoding it becomes `1 6 7 2 6`. For the third operation, after decoding it becomes `0 2`, and $lastans$ is updated to $2$. For the fourth operation, after decoding it becomes `0 11`, and $lastans$ is updated to $0$. For the fifth operation, after decoding it becomes `1 4 7 6 7`. For the sixth operation, after decoding it becomes `0 5`. ### Constraints For $30\%$ of the testdata, $n \leq 10^3$ is guaranteed. For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq k, x_0, x_1 \leq 39989$, $1 \leq y_0, y_1 \leq 10^9$. ### Notes It is not guaranteed that $x_0 \neq x_1$. For a segment with $x_0' = x_1'$, its intersection with $x = x_0'$ is defined to be the endpoint with the larger $y$-coordinate. Translated by ChatGPT 5