logo AlgoBeat OnlineJudge
登录 注册

#103165. [BZOJ 3165] [Heoi2013]Segment

内存限制:256 MiB 时间限制:40000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

要求在平面直角坐标系下维护两个操作:

  1. 在平面上加入一条线段。记第 条被插入的线段的标号为
  2. 给定一个数 ,询问与直线 相交的线段中,交点纵坐标最大的线段的编号。

输入格式

输入的第一行是一个整数 ,代表操作的个数。

接下来 行,每行若干个用空格隔开的整数,第 行的第一个整数为 ,代表第 次操作的类型。

,则后跟一个整数 ,代表本次操作为查询所所有与直线 相交的线段中,交点纵坐标最大的线段编号。

,则后跟四个整数 ,记 。本次操作为插入一条两端点分别为 的线段。

其中 为上次询问的答案,初始时,

输出格式

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

样例

样例输入 #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

数据范围与提示

对于 的数据,保证