#886. [HEOI2013] Segment

    ID: 886 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构线段树贪心块状链表其他分块2013各省省选递归河北块状数组

[HEOI2013] Segment

题目描述

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

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

输入格式

本题输入强制在线

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

接下来 nn 行,每行若干个用空格隔开的整数,第 (i+1)(i + 1) 行的第一个整数为 opop,代表第 ii 次操作的类型。

op=0op = 0,则后跟一个整数 kk,代表本次操作为查询所所有与直线 x=(k+lastans1)mod39989+1x = (k + lastans - 1) \bmod 39989 + 1 相交的线段中,交点纵坐标最大的线段编号。

op=1op = 1,则后跟四个整数 x0,y0,x1,y1x_0, y_0, x_1, y_1,记 xi=(xi+lastans1)mod39989+1x_i' = (x_i + lastans - 1) \bmod 39989 + 1yi=(yi+lastans1)mod109+1y_i' = (y_i + lastans - 1) \bmod 10^9 + 1。本次操作为插入一条两端点分别为 (x0,y0)(x_0', y_0')(x1,y1)(x_1',y_1') 的线段。

其中 lastanslastans 为上次询问的答案,初始时,lastans=0lastans = 0

输出格式

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

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

提示

样例输入输出 11 解释

对于第一次操作,解密后为 1 8 5 10 8

对于第二次操作,解密后为 1 6 7 2 6

对于第三次操作,解密后为 0 2,此时 lastanslastans 被更新为 22

对于第四次操作,解密后为 0 11,此时 lastanslastans 被更新为 00

对于第五次操作,解密后为 1 4 7 6 7

对于第六次操作,解密后为 0 5

数据范围与约定

对于 30%30\% 的数据,保证 n103n \leq 10^3

对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51k,x0,x1399891 \leq k, x_0, x_1 \leq 399891y0,y11091 \leq y_0, y_1 \leq 10^9

提示

不保证 x0x1x_0 \neq x_1。对于一条 x0=x1x_0' = x_1' 的线段,认为其与 x=x0x = x_0' 的交点为其两端点中纵坐标较大的端点。