- 有(q)次操作，分为两种：加入一条线段，询问与直线(x=k)交点纵坐标最大的线段的最小编号。
- (qle10^5,xle39989)，强制在线
李超线段树
第一次写李超线段树，之前遇到过每次插入直线的题目是直接靠线段树上二分过的。。。
其实思想也挺简单的，就是考虑在线段树的每个节点上记录一条线段。
当我们插入一条线段的时候，先找出它的横坐标区间在线段树上对应的点，然后给这些点对应的区间分别执行插入操作。
如果当前点原本没有记录线段，那么就直接记下插入的线段。
否则，我们比较插入线段与记录线段在(x=mid)处的取值，取较优的那条为记录线段，较劣的那条为新的插入线段。
然后分别判断插入线段在左右两区间是否被完全碾压，如果没有被完全碾压就进去继续执行插入操作。
由于不可能在两个区间都没有被完全碾压，因此每次至多进入一个子区间，复杂度就有了保障。
询问时求出根节点到询问点一路上最优的线段即可。
代码：(O(nlog^2n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 100000
#define X 39989
#define Y 1000000000
#define DB double
#define eps 1e-9
using namespace std;
DB k[N+5],b[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('
');}
}using namespace FastIO;
class SegmentTree
{
private:
#define PT CI l=1,CI r=X,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
#define F(id,x) (k[id]*x+b[id])
#define Cmp(x,A,B) (fabs(F(A,x)-F(B,x))<eps?A<B:F(A,x)>F(B,x))
int P[N<<2];
I void T(RI id,PT)//插入线段
{
if(!P[rt]) return (void)(P[rt]=id);RI mid=l+r>>1;//原本没有线段则直接记录
Cmp(mid,id,P[rt])&&(swap(P[rt],id),0);if(l==r) return;//记录较优的，插入较劣的
Cmp(l,id,P[rt])&&(T(id,LT),0),Cmp(r,id,P[rt])&&(T(id,RT),0);//进入未被完全碾压的子区间
}
public:
I void U(CI L,CI R,CI id,PT)//找到横坐标区间对应节点插入
{
if(L<=l&&r<=R) return T(id,l,r,rt);RI mid=l+r>>1;
L<=mid&&(U(L,R,id,LT),0),R>mid&&(U(L,R,id,RT),0);
}
I int Q(CI x,PT)//询问，求出一路上最优的线段
{
if(l==r) return P[rt];RI mid=l+r>>1,t=x<=mid?Q(x,LT):Q(x,RT);
return P[rt]&&t?(Cmp(x,P[rt],t)?P[rt]:t):P[rt]|t;
}
}S;
int main()
{
RI Qt,op,x,y,xx,yy,ct=0,lst=0;read(Qt);W(Qt--)
{
if(read(op),!op) {read(x),writeln(lst=S.Q((x+lst-1)%X+1));continue;}//询问
read(x,y,xx,yy),x=(x+lst-1)%X+1,y=(y+lst-1)%Y+1,xx=(xx+lst-1)%X+1,yy=(yy+lst-1)%Y+1;
if(++ct,x==xx) {k[ct]=1,b[ct]=max(y,yy)-x,S.U(x,x,ct);continue;}//特判与x轴垂直，只取最上方一个点
x>xx&&(swap(x,xx),swap(y,yy),0),k[ct]=1.0*(yy-y)/(xx-x),b[ct]=y-k[ct]*x,S.U(x,xx,ct);//求出解析式，然后插入
}return clear(),0;
}