至今不会李超线段树(.jpg)……
前言
先说明一下，李超线段树只能解决“只插入”的问题，如果有删除恕它无能为力
过程
先考虑这么一个问题，我们要资瓷动态插入直线以及询问直线(x=k)与其它所有直线相交的点中最大的(y)坐标是多少
李超线段树的具体过程是这样的
对于一个区间，我们维护该区间的所有直线中，从上往下去看可以看到它的长度最大的一条直线（即没有被其他直线覆盖的长度最大） （litble语）
我们插入一条直线的时候就需要分类讨论了，以下称插入直线为当前直线，之前的直线为记录直线
1.如果没有记录直线，把记录直线变成当前直线，返回
2.当前直线在这个区间中被记录直线完全覆盖，直接返回
3.当前直线在这个区间中完全覆盖记录直线，把记录直线变成当前直线，返回
4.如果上面情况都不满足，那么这个区间中两条直线显然有交点，我们求出交点的(x)坐标，根据(x)与区间中点的大小关系判断哪条直线未被覆盖的长一点，把记录直线变成长一点的那个，另一条直线继续递归
因为第四步中我们区间长度至少减少一半，所以它的复杂度是(O(nlog n))的
例题
洛谷 P4254 [JSOI2008]Blue Mary开公司
这就是我们之前说的操作啦，直接上李超线段树就行了
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
double readdb()
{
R double x=0,y=0.1,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(x=ch-'0';(ch=getc())>='0'&&ch<='9';x=x*10+ch-'0');
for(ch=='.'&&(ch=getc());ch>='0'&&ch<='9';x+=(ch-'0')*y,y*=0.1,ch=getc());
return x*f;
}
inline char getop(){R char ch;while((ch=getc())!='Q'&&ch!='P');return ch;}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='
';
}
const int N=1e5+5;
struct node{
node *lc,*rc;double b,k,lv,rv;bool flag;
inline void ins(R double bb,R double kk,R int l,R int r){b=bb,k=kk,lv=k*l+b,rv=k*r+b,flag=1;}
inline double val(const R int &x){return k*x+b;}
}pool[N<<2],*rt;int tot;
inline node *newnode(){return &pool[tot++];}
int n,x,q;double b,k,bb,kk,res;char op;
void build(node* &p,int l,int r){
p=newnode();if(l==r)return;
int mid=(l+r)>>1;
build(p->lc,l,mid),build(p->rc,mid+1,r);
}
void query(node *p,int l,int r){
cmax(res,p->val(x));if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)query(p->lc,l,mid);
else query(p->rc,mid+1,r);
}
void update(node *p,int l,int r){
if(!p->flag)return p->ins(b,k,l,r),void();
double lv=l*k+b,rv=r*k+b;
if(lv<=p->lv&&rv<=p->rv)return;
if(lv>p->lv&&rv>p->rv)return p->ins(b,k,l,r),void();
int mid=(l+r)>>1;
double x=(b-p->b)/(p->k-k);
if(lv<=p->lv){
if(x<=mid)bb=p->b,kk=p->k,p->ins(b,k,l,r),b=bb,k=kk,update(p->lc,l,mid);
else update(p->rc,mid+1,r);
}else{
if(x<=mid)update(p->lc,l,mid);
else bb=p->b,kk=p->k,p->ins(b,k,l,r),b=bb,k=kk,update(p->rc,mid+1,r);
}
}
int main(){
// freopen("testdata.in","r",stdin);
n=50000,q=read();
build(rt,1,n);
while(q--){
op=getop();
if(op=='Q')x=read(),res=0,query(rt,1,n),print(res/100);
else b=readdb(),k=readdb(),b-=k,update(rt,1,n);
}
return Ot(),0;
}
洛谷P4097 [HEOI2013]Segment
这里加入的是线段而不是直线，所以得把线段在线段树上对应区间内拆开之后再执行李超线段树的操作，那么复杂度就是(O(nlog^2n))
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='
';
}
const int M=39989,L=1e9,N=1e5+5;
struct node{
node *lc,*rc;double b,k;bool flag;int id;
inline void ins(R double bb,R double kk,R int ii){b=bb,k=kk,id=ii,flag=1;}
inline double calc(const R int &x){return k*x+b;}
}pool[N<<2],*rt;int tot;
int n,q,id,ii,ql,qr,res,x;double b,k,bb,kk,mx;
inline node *newnode(){return &pool[tot++];}
void build(node* &p,int l,int r){
p=newnode();if(l==r)return;
int mid=(l+r)>>1;
build(p->lc,l,mid),build(p->rc,mid+1,r);
}
void update(node *p,int l,int r,double b,double k,int id){
if(ql<=l&&qr>=r){
if(!p->flag)return p->ins(b,k,id),void();
double lv1=l*k+b,rv1=r*k+b,lv2=p->calc(l),rv2=p->calc(r);
if(lv1<=lv2&&rv1<=rv2)return;
if(lv1>lv2&&rv1>rv2)return p->ins(b,k,id),void();
int mid=(l+r)>>1;
double x=(b-p->b)/(p->k-k);
if(lv1<=lv2){
if(x<=mid)bb=p->b,kk=p->k,ii=p->id,p->ins(b,k,id),update(p->lc,l,mid,bb,kk,ii);
else update(p->rc,mid+1,r,b,k,id);
}else{
if(x<=mid)update(p->lc,l,mid,b,k,id);
else bb=p->b,kk=p->k,ii=p->id,p->ins(b,k,id),update(p->rc,mid+1,r,bb,kk,ii);
}
return;
}
int mid=(l+r)>>1;
if(ql<=mid)update(p->lc,l,mid,b,k,id);
if(qr>mid)update(p->rc,mid+1,r,b,k,id);
}
void query(node *p,int l,int r){
if(cmax(mx,p->calc(x)))res=p->id;
if(l==r)return;
int mid=(l+r)>>1;
x<=mid?query(p->lc,l,mid):query(p->rc,mid+1,r);
}
int cnt,op,val[N],ID[N];
int main(){
q=read(),n=39989;
build(rt,1,n);
while(q--){
op=read();
if(op==1){
int x0=(read()+res-1)%n+1,y0=(read()+res-1)%L+1;
int x1=(read()+res-1)%n+1,y1=(read()+res-1)%L+1;
++cnt;
if(x0==x1&&cmax(val[x0],max(y0,y1))){ID[x0]=cnt;continue;}
if(x0>x1)swap(x0,x1),swap(y0,y1);
k=1.0*(y1-y0)/(x1-x0),b=y0-k*x0,id=cnt,ql=x0,qr=x1;
update(rt,1,n,b,k,id);
}else{
x=(read()+res-1)%n+1,mx=res=0;
query(rt,1,n);
cmax(mx,1.0*val[x])?res=ID[x]:0;
print(res);
}
}
return Ot(),0;
}
洛谷P4069 [SDOI2016]游戏
如果我们把路径拆成两段，那么这个路径加可以看成是一个一次函数
具体来说，设(dis_u)表示节点(u)到根节点的距离，那么((x,lca))这条路径上每个节点的权值就会加上(-dis_ua+dis_xa+b)，而((lca,y))这条路径上每个节点就会加上(dis_ua+a(dis_x+2 imes dis_{lca})+b)
区间加一次函数并维护最值，就是李超线段树啦~~~~
我们把它给树剖了，那么同一条重链里(dis)肯定是递增的，我们就可以把插入直线变成插入线段
顺便注意我们的线段树上的节点是离散化之后的，所以在李超线段树计算的时候要用原来的(dis)进行计算
树剖一个(log)，李超线段树两个(log)，总复杂度是(O(nlog^3n))
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define inf 123456789123456789ll
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R ll x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='
';
}
const int N=1e5+5;
struct eg{int v,nx,w;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}
ll dis[N],bb,kk;int dfn[N],rk[N],top[N],fa[N],sz[N],son[N],dep[N];
int n,m,cnt;
void dfs1(int u){
dep[u]=dep[fa[u]]+1,sz[u]=1;
go(u)if(v!=fa[u]){
fa[v]=u,dis[v]=dis[u]+e[i].w,dfs1(v),sz[u]+=sz[v];
sz[v]>sz[son[u]]?son[u]=v:0;
}
}
void dfs2(int u,int t){
rk[dfn[u]=++cnt]=u,top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
go(u)if(!top[v])dfs2(v,v);
}
int LCA(R int u,R int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
struct node{
node *lc,*rc;ll b,k,mn,lv,rv;int flag;
inline void ins(R ll bb,R ll kk,R ll l,R ll r){b=bb,k=kk,lv=k*l+b,rv=k*r+b,cmin(mn,lv),cmin(mn,rv),flag=1;}
inline void upd(){cmin(mn,lc->mn),cmin(mn,rc->mn);}
inline ll calc(R ll x){return k*x+b;}
}pool[N<<2],*rt;int num;
inline node *newnode(){return &pool[num++];}
int ql,qr;ll res,k,b;
void build(node* &p,int l,int r){
p=newnode(),p->b=p->mn=p->lv=p->rv=inf,p->k=0;
if(l==r)return;
int mid=(l+r)>>1;
build(p->lc,l,mid),build(p->rc,mid+1,r);
}
void update(node *p,int l,int r,ll b,ll k){
if(ql<=l&&qr>=r){
int mid=(l+r)>>1;
ll dl=dis[rk[l]],dr=dis[rk[r]],dm=dis[rk[mid]];
if(!p->flag)return p->ins(b,k,dl,dr),void();
ll lv=dl*k+b,rv=dr*k+b;
if(lv>=p->lv&&rv>=p->rv)return;
if(lv<p->lv&&rv<p->rv)return p->ins(b,k,dl,dr),void();
double x=1.0*(b-p->b)/(p->k-k);
if(lv<=p->lv){
if(x<=dm)update(p->lc,l,mid,b,k);
else bb=p->b,kk=p->k,p->ins(b,k,dl,dr),update(p->rc,mid+1,r,bb,kk);
}else{
if(x<=dm)bb=p->b,kk=p->k,p->ins(b,k,dl,dr),update(p->lc,l,mid,bb,kk);
else update(p->rc,mid+1,r,b,k);
}
p->upd();
return;
}
int mid=(l+r)>>1;
if(ql<=mid)update(p->lc,l,mid,b,k);
if(qr>mid)update(p->rc,mid+1,r,b,k);
p->upd();
}
void query(node *p,int l,int r){
if(ql<=l&&qr>=r)return cmin(res,p->mn),void();
cmin(res,p->calc(dis[rk[max(l,ql)]])),
cmin(res,p->calc(dis[rk[min(r,qr)]]));
int mid=(l+r)>>1;
if(ql<=mid)query(p->lc,l,mid);
if(qr>mid)query(p->rc,mid+1,r);
}
void change(int u,int v){
while(top[u]!=top[v]){
ql=dfn[top[u]],qr=dfn[u],
update(rt,1,n,b,k),
u=fa[top[u]];
}
ql=dfn[v],qr=dfn[u],update(rt,1,n,b,k);
}
void ask(int u,int v){
res=inf;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
ql=dfn[top[u]],qr=dfn[u],query(rt,1,n),
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
ql=dfn[v],qr=dfn[u],query(rt,1,n);
print(res);
}
int op,u,v,A,B,lca;
signed main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();
for(R int i=1,u,v,w;i<n;++i)u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
dfs1(1),dfs2(1,1),build(rt,1,n);
while(m--){
op=read(),u=read(),v=read();
if(op==2)ask(u,v);
else{
lca=LCA(u,v),A=read(),B=read();
b=dis[u]*A+B,k=-A,change(u,lca);
b=(dis[u]-(dis[lca]<<1))*A+B,k=A,change(v,lca);
}
}
return Ot(),0;
}
参考文章：