最经典应用就是维护一个二维平面直角坐标系，支持动态插入线段（理解为有值域的一次函数 \(y=kx+b\) ），询问已插入线段与直线 \(x=x_0\) 交点的纵坐标最值。
即当 \(x=x_0\) ，求 \(max\) 或 \(min\) { \(k_ix+b_i\) }
对于普通求法的 \(O(n)\) 遍历，如何优化时间复杂度呢？其实就是找一种方法减少有效集合大小，而李超线段树就是如此。
单次查询是 \(O(logn)\) 的，修改是 \(O(log^2n)\) 的。
现在我们需要插入一条线段 f，在这条线段完整覆盖的线段树节点代表的区间中，某些区间的最优线段可能发生改变。
考虑某个被新线段 f 完整覆盖的区间，若该区间无最优线段，则该线段可以直接成为最优线段。
否则，设该区间的中点为 mid，我们拿新线段 f 在中点处的值与原最优线段 g 在中点处的值作比较。
如果新线段 f 更优，则将 f 和 g 交换。
那么现在考虑在中点处 f 不如 g 优的情况：
若在左端点处 f 更优，那么f 和 g 必然在左半区间中产生了交点，递归到左儿子中进行插入；
若在右端点处 f 更优，那么 f 和 g 必然在右半区间中产生了交点，递归到右儿子中进行插入。
若在左右端点处 g 都更优，那么 f 不可能成为答案，不需要继续下传。
这个方法的优势就在于不需要讨论斜率的正负，十分方便。
//李超线段树 模版 [HEOI2013] Segment
#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
#define pdi pair<double,int>
using namespace std;
const double eps=1e-9;//精度问题
const int maxn=1e5+5,mod1=39989,mod2=1000000000;
int n,cnt,ans,t[maxn<<1];
struct node{
double k,b;
}p[maxn];
int cmp(double x,double y){
if(x-y>eps) return 1;
if(y-x>eps) return -1;
return 0;
}
double f(int id,int x){
return p[id].b+p[id].k*x;
}
void add(int x,int y,int xx,int yy){
cnt++;
if(x==xx) p[cnt].k=0,p[cnt].b=max(y,yy);//特判直线斜率不存在的情况！
else p[cnt].k=1.0*(yy-y)/(xx-x),p[cnt].b=y-p[cnt].k*x;
}
void upd(int id,int l,int r,int u){//对线段完全覆盖到的区间进行修改
int &v=t[id],mid=(l+r)>>1;
int tmp=cmp(f(u,mid),f(v,mid));
if(tmp==1||(!tmp&&u<v)) swap(u,v);//交换新旧线段，这里是取地址的
int tl=cmp(f(u,l),f(v,l)),tr=cmp(f(u,r),f(v,r));
if(tl==1||(!tl&&u<v)) upd(lid,l,mid,u);
if(tr==1||(!tr&&u<v)) upd(rid,mid+1,r,u);
}
void change(int id,int l,int r,int vl,int vr,int u){
if(vl<=l&&r<=vr){
upd(id,l,r,u);
return ;
}
int mid=(l+r)>>1;//线段树的查询
if(vl<=mid) change(lid,l,mid,vl,vr,u);
if(mid<vr) change(rid,mid+1,r,vl,vr,u);
}
pdi pmax(pdi x,pdi y){
if(cmp(x.first,y.first)==-1) return y;
else if(cmp(x.first,y.first)==1) return x;
else return x.second<y.second?x:y;
}
pdi query(int id,int l,int r,int pos){
if(r<pos||pos<l) return {0,0};//一种比较方便的写法
double res=f(t[id],pos);
if(l==r) return {res,t[id]};
int mid=(l+r)>>1;
return pmax({res,t[id]},pmax(query(lid,l,mid,pos),query(rid,mid+1,r,pos)));
}
int main(){
scanf("%d",&n);
while(n--){
int op;
scanf("%d",&op);
if(op==1){
int x,y,xx,yy;
scanf("%d%d%d%d",&x,&y,&xx,&yy);
x=(x+ans-1+mod1)%mod1+1;
xx=(xx+ans-1+mod1)%mod1+1;
y=(y+ans-1+mod2)%mod2+1;
yy=(yy+ans-1+mod2)%mod2+1;
if(x>xx) swap(x,xx),swap(y,yy);
add(x,y,xx,yy);
change(1,1,mod1,x,xx,cnt);
}
else{
int x;
scanf("%d",&x);
x=(x+ans-1+mod1)%mod1+1;
ans=query(1,1,mod1,x).second;
printf("%d\n",ans);
}
}
return 0;
}