李超线段树学习笔记
用途
李超线段树的用法非常固定，一般就是让你求对于给出的一些线段或直线中，对于某个x最大的y是那个。
通常可以用于斜率优化。
而其的时间复杂度是 \(O(n\log n^2)\)
思路
注：下文默认是线段，因为直线也只用改一下就行了。
我们建立一颗线段树，每个节点保存在当前区间，当x=mid时最大的线段的编号。
然后每次将两条线段进行比较，因为两条线段要么被另一条线段完全覆盖，要么只会覆盖左右区间中的一个（因为交点最多只有一个）。所以对于完全覆盖的，直接选择那一条直线，覆盖一半的，递归查找就行。
对于标记下传的话不太好直接下传，我们可以用标记永久化来做即可。注意因为是浮点数计算，注意要使用eps来判相等。
code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=100011;
int p[N<<2];
double k[N],b[N];
double clac(int id,int x){
return 1.0*k[id]*x+1.0*b[id];
}
int cnt=0;
struct dot{
int xx,yy;
}e1,e2;
double eps=0.0000000001;
void update(int rt,int l,int r,int u){
int mid=(l+r)>>1;
if(!p[rt]){
p[rt]=u;
// cout<<"u:"<<u<<endl;
return ;
}
if(l==r){
int f=clac(u,mid);//bianhao
int g=clac(p[rt],mid);
if(f-g>eps)swap(p[rt],u);
if(abs(f-g)<eps&&u<p[rt])p[rt]=u;
return ;
}
else{
// cout<<"cnt:"<<u<<" "<<p[rt]<<" "<<l<<" "<<r<<endl;
double f=clac(u,mid);//bianhao
double g=clac(p[rt],mid);
// cout<<"l,r.f,g:"<<l<<" "<<r<<" "<<f<<" "<<g<<endl;
if(f-g>eps)swap(p[rt],u);
// cout<<u<<" "<<p[rt]<<endl;
if(clac(u,l)-clac(p[rt],l)>eps||(abs(clac(u,l)-clac(p[rt],l))<eps&&u<p[rt]))update(rt<<1,l,mid,u);
if(clac(u,r)-clac(p[rt],r)>eps||(abs(clac(u,r)-clac(p[rt],r))<eps&&u<p[rt]))update(rt<<1|1,mid+1,r,u);
}
}
void change(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){
// cout<<"l,r:"<<l<<" "<<r<<endl;
update(rt,l,r,cnt);
return ;
}
int mid=(l+r)>>1;
if(L<=mid)change(rt<<1,l,mid,L,R);
if(mid+1<=R)change(rt<<1|1,mid+1,r,L,R);
return ;
}
int lastans,ans;
double ansy;
void ask(int rt,int l,int r,int d){
int mid=(l+r)>>1;
double sum=clac(p[rt],d);
if(sum-ansy>eps){
ansy=sum;
ans=p[rt];
}
if(abs(sum-ansy)<eps&&p[rt]<ans){
ans=p[rt];
ansy=sum;
}
if(l==r){
lastans=ans;
cout<<lastans<<endl;
ansy=0;ans=0;
return ;
}
if(d<=mid)ask(rt<<1,l,mid,d);
else ask(rt<<1|1,mid+1,r,d);
return ;
}
#define mod 1000000000
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int op,t;
cin>>op;
if(op==0){
cin>>t;
int x=(t+lastans-1)%39989+1;
ask(1,1,39989,x);
}
else{
cin>>e1.xx>>e1.yy>>e2.xx>>e2.yy;
e1.xx=(e1.xx+lastans-1)%39989+1;
e2.xx=(e2.xx+lastans-1)%39989+1;
e1.yy=(e1.yy+lastans-1)%mod+1;
e2.yy=(e2.yy+lastans-1)%mod+1;
if(e1.xx>e2.xx)swap(e1,e2);
cnt++;
// cout<<e1.xx<<" "<<e1.yy<<" "<<e2.xx<<" "<<e2.yy<<endl;
if(e1.xx==e2.xx){
k[cnt]=0;
b[cnt]=max(e1.yy,e2.yy);
}
else{
k[cnt]=(1.0*(e2.yy-e1.yy))/(1.0*(e2.xx-e1.xx));
b[cnt]=e1.yy-e1.xx*k[cnt];
}
// cout<<k[cnt]<<" "<<b[cnt]<<endl;
change(1,1,39989,e1.xx,e2.xx);
}
}
}