BZOJ 3165: [Heoi2013]Segment

正文索引 [隐藏]

Description

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

Input

第一行一个整数n,表示共n 个操作。
接下来n行,每行第一个数为0或1。
若该数为 0,则后面跟着一个正整数 k,表示询问与直线
x = ((k +lastans–1)%39989+1)相交的线段中交点(包括在端点相交的情形)最靠上的线段的编号,其中%表示取余。若某条线段为直线的一部分,则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求,输出编号最小的线段的编号。
若该数为 1,则后面跟着四个正整数 x0, y0, x 1, y 1,表示插入一条两个端点为
((x0+lastans-1)%39989+1,(y0+lastans-1)%109+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%109+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。

Output

对于每个 0操作,输出一行,包含一个正整数,表示交点最靠上的线段的编
号。若不存在与直线相交的线段,答案为0。

Sample Input

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

Sample Output

2
0 3

HINT

对于100%的数据,1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

题解

这道题目竟然是用线段树,我一开始就被它计算几何的假象吓住了!
我们可以把X轴想象成一颗线段树,然后用输入的线段来覆盖它。
如果新加入的线段在原来树上线段的上方,那毫无疑问就可以覆盖。
如果新加入的线段与原来树上线段有交点,那么我们计算出交点在哪边,更新交点那边的子树的线段。原树上线段取在上方更长的那个!

代码

 数据>.<好孩子看不见

链接:http://pan.baidu.com/s/1c0GVnyS 密码:jdta