所谓李超线段树就是解决此题一类的问题（线段覆盖查询点最大（小）），把原本计算几何的题目变成了简单的线段树，巧妙地结合了线段树的标记永久化与标记下传，在不考虑精度误差的影响下，打法应该是这样的。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid(a,b) ((a+b)>>1)
typedef long double ld;
const int Inf_x=;
const int Inf_y=;
int cnt,sz;
struct Line{
ld k,b;int id;
inline ld f(int x){return k*x+b;}
inline ld point(Line a){return (b-a.b)/(a.k-k);}
};
struct lcSegment_Tree{
lcSegment_Tree *ch[];
Line line;
}seg[Inf_x<<],*root;
void pushdown(lcSegment_Tree *p,int l,int r,Line line){
ld a1=p->line.f(l),a2=line.f(l),b1=p->line.f(r),b2=line.f(r);
if(a1<=a2&&b1<=b2){p->line=line;return;}
if(a1>a2&&b1>b2)return;
ld x=line.point(p->line);
if(x<=mid(l,r)){
if(a1>a2)pushdown(p->ch[],l,mid(l,r),p->line),p->line=line;
else pushdown(p->ch[],l,mid(l,r),line);
}else{
if(a1>a2)pushdown(p->ch[],mid(l,r)+,r,line);
else pushdown(p->ch[],mid(l,r)+,r,p->line),p->line=line;
}
}
void build(lcSegment_Tree *&p,int l,int r){
p=seg+sz,++sz;
if(l==r)return;
build(p->ch[],l,mid(l,r));
build(p->ch[],mid(l,r)+,r);
}
void insert(lcSegment_Tree *p,int l,int r,int z,int y,Line line){
if(z<=l&&r<=y){pushdown(p,l,r,line);return;}
if(z<=mid(l,r))insert(p->ch[],l,mid(l,r),z,y,line);
if(mid(l,r)<y)insert(p->ch[],mid(l,r)+,r,z,y,line);
}
void query(lcSegment_Tree *p,int l,int r,int pos,ld last,int &ans){
if(p->line.f(pos)>last||(p->line.f(pos)==last&&p->line.id<ans))ans=p->line.id,last=p->line.f(pos);
if(l==r)return;
if(pos<=mid(l,r))query(p->ch[],l,mid(l,r),pos,last,ans);
else query(p->ch[],mid(l,r)+,r,pos,last,ans);
}
int main(){
int T,opt,zzh1,zzh2,wq1,wq2,lastans=,x;Line temp;
scanf("%d",&T),build(root,,Inf_x);
while(T--){
scanf("%d",&opt);
if(opt){
scanf("%d%d%d%d",&zzh1,&zzh2,&wq1,&wq2);
zzh1=(zzh1+lastans-)%Inf_x+,zzh2=(zzh2+lastans-)%Inf_y+,
wq1=(wq1+lastans-)%Inf_x+,wq2=(wq2+lastans-)%Inf_y+;
if(wq1>zzh1)wq1^=zzh1^=wq1^=zzh1,wq2^=zzh2^=wq2^=zzh2;
if(wq1==zzh1)temp.k=.,temp.b=std::max(wq2,zzh2);
else temp.k=(ld)(zzh2-wq2)/(zzh1-wq1),temp.b=zzh2-temp.k*zzh1;
temp.id=++cnt,insert(root,,Inf_x,wq1,zzh1,temp);
}else{
scanf("%d",&x),x=(x+lastans-)%Inf_x+,lastans=;
query(root,,Inf_x,x,.,lastans);
printf("%d\n",lastans);
}
}return ;
}