李超线段树学习笔记
李超线段树，是一种维护一次函数最值的数据结构，其结构类似于线段树，由大神李超发明，故称之为李超线段树。
前置知识：
1.线段树
2.求两直线交点坐标
代码在这里：
#define N 100500
struct node{
int l,r,id;
}t[N<<2];
#define lc x<<1
#define db double
#define rc x<<1|1
db fabs(db a){
return (a<0)?-a:a;
}
void build(int x,int l,int r){
t[x].l=l,t[x].r=r;
if(l==r)return ;
int mid=l+r>>1;
build(lc,l,mid);build(rc,mid+1,r);
}
int cnt,x1[N],y1[N],x2[N],y2[N];
struct line{
db k,b;
}in[N];
void add(int id){
if(x1[id]==x2[id]){
in[id].k=0;in[id].b=max(y1[id],y2[id]);
return ;
}
in[id].k=1.0*(y1[id]-y2[id])/(x1[id]-x2[id]);
in[id].b=(db)y1[id]-in[id].k*x1[id];
}
李超线段树资瓷2个基本操作：
- 插入一条线段\((x_0,y_0,x_1,y_1)\)
- 给定整数\(k\)，支持查询给定线段中\(x=k\)时的最大纵坐标及其所属线段。
其核心思想是，对于每个区间，它所存储的是优势最大的线段(在最高折线中有最长的一段)。
划分区间的方案类似于线段树。
类比线段树，李超线段树的查询也是对于区间进行的，一次查询就枚举所有的李超线段树里包含\(k\)的区间的最优势线段，对所有的最优势线段取\(\max\)即可。
#define pr pair<db,int>
#define mk make_pair
pr fmax(pr a,pr b){
if(fabs(a.first-b.first)<1e-9){
if(a.second>b.second)return b;
return a;
}
return max(a,b);
}
pr find(int x,int k){
pr ans;
int y=t[x].id;
if(t[x].l==t[x].r)return mk(get(y,k),y);
if(y)ans=mk(get(y,k),y);
else ans=mk(0,0);
if(k<=t[lc].r)ans=fmax(ans,find(lc,k));
else ans=fmax(ans,find(rc,k));
return ans;
}
问题在于插入：
下面我们来分类讨论插入线段\(x\)：
- 区间里原本没有线段->直接更新
- 区间原有线段\(rt\),对其进行比较：
我们取中点\(mid\)的值来进行对比，如下图：
就会神秘的发现：
在\(mid\)处取值更大的线段就是这个区间的最大优势线段
此时我们将最大优势线段更新，如果\(x\)优于\(rt\)，就执行swap(x,rt)(此时\(rt\)就成了新插入的线段)但，这就完了吗?
不一定，新插入的线段即使不是当前区间的最大优势线段，也有可能更新儿子区间。
仍然是之前那张图。容易发现，若\(y_{x,r}>y_{rt,r}\)，则\(x\)可能更新右儿子。同理，若\(y_{x,l}>y_{rt,l}\)则有可能更新左儿子，这些都进行递归处理即可。
复杂度的话，由于\(y_{x,mid}<y_{rt,mid}\)，所以最多递归一个儿子(瞎胡的，欢迎斧正)，所以应该是\(O(n\log^2 n)\)的样子。
所以代码实际肥肠简单。
void updata(int x,int k){
int mid=t[x].l+t[x].r>>1;
if(get(t[x].id,mid)<=get(k,mid))swap(k,t[x].id);
if(t[x].l==t[x].r)return ;
if(get(t[x].id,t[x].l)<get(k,t[x].l)||(
get(t[x].id,t[x].l)==get(k,t[x].l)&&t[x].id>k))updata(lc,k);
if(get(t[x].id,t[x].r)<get(k,t[x].r)||(
get(t[x].id,t[x].r)==get(k,t[x].r)&&t[x].id>k))updata(rc,k);//这里是因为题目要求编号最小
}
void change(int x,int l,int r,int k){
if(l<=t[x].l&&t[x].r<=r){
updata(x,k);
return ;
}
int mid=t[x].l+t[x].r>>1;
if(l<=mid)change(lc,l,r,k);
if(mid<r)change(rc,l,r,k);
}
同理，如果是求最小的话反过来就是了。
以模板题HEOI2016线段树为例：
#include<iostream>
#include<cstdio>
using namespace std;
#define N 100500
struct node{
int l,r,id;
}t[N<<2];
#define lc x<<1
#define db double
#define rc x<<1|1
db fabs(db a){
return (a<0)?-a:a;
}
void build(int x,int l,int r){
t[x].l=l,t[x].r=r;
if(l==r)return ;
int mid=l+r>>1;
build(lc,l,mid);build(rc,mid+1,r);
}
int cnt,x1[N],y1[N],x2[N],y2[N];
struct line{
db k,b;
}in[N];
void add(int id){
if(x1[id]==x2[id]){
in[id].k=0;in[id].b=max(y1[id],y2[id]);
return ;
}
in[id].k=1.0*(y1[id]-y2[id])/(x1[id]-x2[id]);
in[id].b=(db)y1[id]-in[id].k*x1[id];
}
db get(int id,int x){
return (db)in[id].k*x+in[id].b;
}
#define pr pair<db,int>
#define mk make_pair
pr fmax(pr a,pr b){
if(fabs(a.first-b.first)<1e-9){
if(a.second>b.second)return b;
return a;
}
return max(a,b);
}
pr find(int x,int k){
pr ans;
int y=t[x].id;//cout<<x<<" "<<t[x].l<<" "<<t[x].r<<" "<<y<<endl;
if(t[x].l==t[x].r)return mk(get(y,k),y);
if(y)ans=mk(get(y,k),y);
else ans=mk(0,0);
if(k<=t[lc].r)ans=fmax(ans,find(lc,k));
else ans=fmax(ans,find(rc,k));
return ans;
}
void updata(int x,int k){
int mid=t[x].l+t[x].r>>1;
if(get(t[x].id,mid)<=get(k,mid))swap(k,t[x].id);
if(t[x].l==t[x].r)return ;
if(get(t[x].id,t[x].l)<get(k,t[x].l)||(
get(t[x].id,t[x].l)==get(k,t[x].l)&&t[x].id>k))updata(lc,k);
if(get(t[x].id,t[x].r)<get(k,t[x].r)||(
get(t[x].id,t[x].r)==get(k,t[x].r)&&t[x].id>k))updata(rc,k);
}
void change(int x,int l,int r,int k){
if(l<=t[x].l&&t[x].r<=r){
updata(x,k);
return ;
}
int mid=t[x].l+t[x].r>>1;
if(l<=mid)change(lc,l,r,k);
if(mid<r)change(rc,l,r,k);
}
int lst,n;
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
build(1,1,40000);
for(int i=1;i<=n;i++){
int op;cin>>op;
if(!op){
int k;cin>>k;k=(k+lst+39988)%39989+1;
lst=find(1,k).second;
cout<<lst<<"\n";
}
else {
swap(++cnt,i);
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
x1[i]=(x1[i]+lst+39988)%39989+1;
x2[i]=(x2[i]+lst+39988)%39989+1;
y1[i]=(y1[i]+lst+999999999)%1000000000+1;
y2[i]=(y2[i]+lst+999999999)%1000000000+1;
if(x1[i]>x2[i]){
swap(x1[i],x2[i]);
swap(y1[i],y2[i]);
}
add(i);
// cout<<in[i].k<<" "<<in[i].b<<endl;
change(1,x1[i],x2[i],i);
swap(i,cnt);
}
}
}
而因为李超线段树的特性，也被用于斜率优化，主要是将斜率式转化为点斜式方程\(y=kx+b\)，然后就每次需要查询\(y=0\)时的最小/大值，就是所求的最小/大截距。这样就不需要考虑二分了。尤其是方便分不清楚大于小于的同学，付出一个\(O(\log n)\)的代价，换回了绝大部分分数(常熟小可以到一百)。虽然李超不见得多好写.