【模板】李超线段树 / [HEOI2013] Segment

题目描述

要求在平面直角坐标系下维护两个操作: 1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。 2. 给定一个数 $k$,询问与直线 $x = k$ 相交的线段中,交点纵坐标最大的线段的编号。

输入输出格式

输入格式


**本题输入强制在线**。 输入的第一行是一个整数 $n$,代表操作的个数。 接下来 $n$ 行,每行若干个用空格隔开的整数,第 $i + 1$ 行的第一个整数为 $op$,代表第 $i$ 次操作的类型。 若 $op = 0$,则后跟一个整数 $k$,代表本次操作为查询所所有与直线 $x = (k + lastans - 1) \bmod 39989 + 1$ 相交的线段中,交点纵坐标最大的线段编号。 若 $op = 1$,则后跟四个整数 $x_0, y_0, x_1, y_1$,记 $x_i' = (x_i + lastans - 1) \bmod 39989 + 1$,$y_i' = (y_i + lastans - 1) \bmod 10^9 + 1$。本次操作为插入一条两端点分别为 $(x_0', y_0')$,$(x_1',y_1')$ 的线段。 其中 $lastans$ 为上次询问的答案,初始时,$lastans = 0$。

输出格式


对于每次查询,输出一行一个整数,代表交点纵坐标最大的线段的编号。若不存在任何一条线段与查询直线有交,则输出 $0$;若有多条线段与查询直线的交点纵坐标都是最大的,则输出编号最小的线段,同时 $lastans$ 也应更新为编号最小的一条线段。

输入输出样例

输入样例 #1

6 
1 8 5 10 8 
1 6 7 2 6 
0 2 
0 9 
1 4 7 6 7 
0 5

输出样例 #1

2 
0 
3

说明

### 样例 $1$ 解释 对于第一次操作,解密后为 `1 8 5 10 8`。 对于第二次操作,解密后为 `1 6 7 2 6`。 对于第三次操作,解密后为 `0 2`,此时 $lastans$ 被更新为 $2$。 对于第四次操作,解密后为 `0 11`,此时 $lastans$ 被更新为 $0$。 对于第五次操作,解密后为 `1 4 7 6 7`。 对于第六次操作,解密后为 `0 5`。 ### 数据范围与约定 对于 $30\%$ 的数据,保证 $n \leq 10^3$。 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^5$,$1 \leq k, x_0, x_1 \leq 39989$,$1 \leq y_0, y_1 \leq 10^9$。 ### 提示 不保证 $x_0 \neq x_1$。对于一条 $x_0' = x_1'$ 的线段,认为其与 $x = x_0'$ 的交点为其两端点中纵坐标较大的端点。