??作为一种先进的数据结构，李超线段树最经典的应用是维护二维平面直角坐标系，支持动态插入线段（不支持删除线段），询问已插入直线和直线 x = x 0 x=x_0 x=x0 相交 y y y 最大值/最小值。插入直线的复杂性 O ( n l o g n ) O(nlogn) O(nlogn)，插入指定区间的线段的复杂性 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)。

??对于上述问题，暴力显然是 O ( n ) O(n) O(n) 所有已插入线段并比较交点的遍历 y y y 值。这种做法复杂性的瓶颈在于我们的最佳解决方案太大，事实上，有些线段根本不能成为最佳解决方案，所以李超线段树使用这种方法来减少最佳解决方案的复杂性。

??首先，李超线段树的每个区间只记录可能成为当前范围内最优解的线段，即该线段在当前区间的个取值上有最优解，我们称这样的线段为优势线段。如何维护区间内的优势线段就成了李超数的核心问题，我们将使用线段树的框架并且利用标记永久化这一方法，接着来具体分析这一问题：

我们以求最大值为例进行分析：

1.当区间内没有任何线段时：我们直接将线段放入当前区间即可

2.当区间内存在旧线段，且新线段的斜率大于旧线段的斜率时，设当前区间中点为 m i d mid mid：

• 如果新线段在中点的值大于旧线段，那么新线段在 [ m i d + 1 , R ] [mid+1,R] [mid+1,R] 上整体取值都比旧线段更优，我们直接用新线段替换旧线段，并且此时旧线段仍可能在 [ L , m i d ] [L,mid] [L,mid] 区间有优势，我们把旧线段下放至 [ L , m i d ] [L,mid] [L,mid] 区间即可
• 如果新线段在中点的值小于旧线段，那么旧线段在 [ L , m i d ] [L,mid] [L,mid] 上整体取值一定都比旧线段更优， 而在 [ m i d + 1 , R ] [mid+1,R] [mid+1,R] 区间新线段仍可能存在优势，所以旧线段仍然是 [ L , R ] [L,R] [L,R] 的优势线段，所以我们保留旧线段，下放线段至 [ m i d + 1 , R ] [mid+1,R] [mid+1,R]

3.当区间内存在旧线段，且新线段的斜率小于旧线段的斜率时同上

4.当区间内存在旧线段，且新线段的斜率相同时，显然我们只需要保留截距更大的线段即可

5.上述过程已经可以很好的维护优势线段，但是在此之前我们可以先判断两条线段是否存在严格优势关系，如果存在我们可以直接排除另一条线段，这样我们在情况 2,3 时就可以保证下放的线段不是毫无用处的，相当于做一个小剪枝

可以发现上述过程中我们维护的所谓优势线段，并不是严格的，复杂度因此有了保障。但是我们在查询的时候显然不能只递归到一个叶子节点，我们必须在向下递归的同时计算经过的线段的最值，即利用标记永久化来得到最优解。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+10;
const int maxm=2e5+10;
const int p=998244353;

int k[maxm],b[maxm];
int tag0[maxn<<2],tag1[maxn<<2];
int n,m,tot=0;

inline ll cal(int i,int x){ 
        
    return 1ll*k[i]*x+b[i];
}

void modify_min(int l,int r,int x,int i){ 
        
    if(!tag0[x]){ 
        tag0[x]=i;return;}
    if(l==r){ 
        
        if(cal(tag0[x],l)>cal(i,l)) tag0[x]=i;
        return;
    }
    int mid=l+r>>1;
    ll y1=cal(tag0[x],mid),y2=cal(i,mid);
    if(k[tag0[x]]>k[i]){ 
        
        if(y1<=y2) modify_min(mid+1,r,x<<1|1,i);
        else modify_min(l,mid,x<<1,tag0[x]),tag0[x]=i;
    }
    else if(k[tag0[x]]<k[i]){ 
        
        if(y1<=y2) modify_min(l,mid,x<<1,i); 
        else modify_min(mid+1,r,x<<1|1,tag0[x]),tag0[x]=i;
    }
    else if(b[tag0[x]]>b[i]) tag0[x]=i;
}

void modify_max(int l,int r,int x,int i){ 
        
    if(!tag1[x]){ 
        tag1[x]=i;return;}
    if(l==r){ 
        
        if(cal(tag1[x],l)<cal(i,l)) tag1[x]=i;
        return;
    }
    int mid=l+r>>1;
    ll y1=cal(tag1[x],mid),y2=cal(i,mid);
    if(k[tag1[x]]>k[i]){ 
        
        if(y1<=y2) modify_max(mid+1,r,x<<1|1,tag1[x]),tag1[x]=i;
        else modify_max(l,mid,x<<1,i);
    }
    else if(k[tag1[x]]<k[i]){ 
        
        if(y1<=y2) modify_max(l,mid,x<<1,tag1[x]),tag1[x]=i;
        else modify_max(mid+1,r,x<<1|1,i);
    }
    else if(b[tag1[x]]<b[i]) tag1[x]=i;
}

ll query_min(int l,int r,int x,int pos){ 
        
    if(tag0[x]==0) return 1e18;
    if(l==r) return cal(tag0[x],pos);
    int mid=l+r>>1;
    ll ans=cal(tag0[x],pos);
    if(pos<=mid) return min(ans,query_min(l,mid,x<<1,pos));
    else return min(ans,query_min(mid+1,r,x<<1|1,pos));
}

ll query_max(int l,int r,int x,int pos){ 
        
    if(tag1[x]==0) return -1e18;
    if(l==r) return cal(tag1[x],pos);
    int mid=l+r>>1;
    ll ans=cal(tag1[x],pos);
    if(pos<=mid) return max(ans,query_max(l,mid,x<<1,pos));
    else return max(ans,query_max(mid+1,r,x<<1|1,pos));
}


int main(){ 
        
    scanf("%d %d",&n,&m);
    int opt;
    while(m--){ 
        
        scanf("%d",&opt);
        if(opt==0){ 
        
            ++tot;
            scanf("%d %d",&k[tot],&b[tot]);
            modify_min(1,n,1,tot);
            modify_max(1,n,1,tot);
        }
        else{ 
        
            int x;
            scanf("%d",&x);
            printf("%lld %lld\n",query_max(1,n,1,x),query_min(1,n,1,x));
        }
    }
    return 0;
}

上述代码同时用多个函数实现了最大最小值，其实只用一个求最大值的模板代替，当我们求求最小值的时候就把直线 y = k x + b y=kx+b y=kx+b 关于 x x x 轴对称的直线 y = − k x − b y=-kx-b y=−kx−b 插入， 我们对所有直线关于 x x x 轴的对称的直线的最大交点，就是求所有直线的最小交点，并且最后查询的时候返回一个值的相反数即可。

两道板子题

题意： 现在有 n n n 次询问，要求支持如下两种操作：

• 1. 1. 1. 插入一个形如 y = k x + b y=kx+b y=kx+b 的一次函数
• 2. 2. 2. 查询已插入直线中与直线 x = T x=T x=T 交点的最大 y y y 值

思路： 李超树模板，注意题目给出的截距要大 1 1 1，调整下即可。

code:

const int maxn=1e5+10;
const int n=50000;

int q,tot=0;
char ch[10];
int tag[maxn<<2];
double k[maxn],b[maxn];

inline double cal(int i,int x){ 
        
    return k[i]*(x-1)+b[i];
}

void modify(int l,int r,int x,int idx){ 
        
    if(l==r){ 
        
        if(cal(tag[x],l)<cal(idx,l)) tag[x]=idx;
        return;
    }
    if(!tag[x]){ 
        tag[x]=idx;return;}
    int mid=l+r>>1;
    double y1=cal(tag[x],mid),y2=cal(idx,mid);
    if(k[tag[x]]<k[idx]){ 
        
        if(y1<=y2) modify(l,mid,x<<1,tag[x]),tag[x]=idx;
        else modify(mid+1,r,x<<1|1,idx);
    }
    else if(k[tag[x]]>k[idx]){ 
        
        if(y1<=y2) modify(mid+1,r,x<<1|1,tag[x]),tag[x]=idx;
        else modify(l,mid,x<<1,idx);
    }
    else if(b[tag[x]]<b[idx]) tag[x]=idx;
}

double query(int l,int r,int x,int pos){ 
        
    if(l==r) return cal(tag[x],l);
    double ans=cal(tag[x],pos);
    int mid=l+r>>1;
    if(pos<=mid) ans=max(ans,query(l,mid,x<<1,pos));
    else ans=max(ans,query(mid+1,r,x<<1|1,pos));
    return ans;
}

int main(){ 
        
    scanf("%d",&q);
    while(q--){ 
        
        scanf("%s",ch);
        if(ch[0]=='P'){ 
        
            tot++;
            scanf("%lf %lf",&b[tot],&k[tot]);
            modify(1,n,1,tot);
        }
        else{ 
        
            int x;
            scanf("%d",&x);
            if(!tot){ 
        
                puts("0");continue;
            }
            printf("%d\n",(int)query(1,n,1,x)/100);
        }
    }
    return 0;
}

题意： 要求在平面直角坐标系下维护两个操作：

• 1. 1. 1. 在平面上加入一条线段。记第 i i i 条被插入的线段的标号为 i i i。
• 2. 2. 2. 给定一个数 k k k，询问与直线 x = k x=k x=k 相交的线段中，交点纵坐标最大的线段的编号

思路：这题和之前插入的稍微有点区别，这道题是插入线段，相当于一条只在指定区间存在的直线，我们只需要按照线段树区间修改框架，只在当前区间属于 [ L , R ] [L,R] [L,R] 内放入线段即可。 [ L , R ] [L,R] [L,R] 在线段树上至多对应 l o g n logn logn 个区间，每次进入一个区间维护优势线段复杂度也是 O ( l o g n ) O(logn) O(logn)，总复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

code:

const int maxn=1e5+10;
const int n=39989;
const int p=1e9;


int q,op,lastans,L,R;
int tot;
double k[maxn],b[maxn];
int tag[maxn<<2];
bool f;

inline double cal(int i,int x){ 
        
    return k[i]*x+b[i];
}

void modify(int l,int r,int x,int idx){ 
        
    if(L<=l&&r<=R){ 
        
        if(l==r){ 
        
            if(cal(tag[x],l)<cal(idx,l)) tag[x]=idx;
            return;
        }
        if(!tag[x]){ 
        tag[x]=idx;return;}
        int mid=l+r>>1;
        double y1=cal(tag[x],mid),y2=cal(idx,mid);
        if(k[tag[x]]<k[idx]){ 
        
            if(y1<=y2) modify(l,mid,x<<1,tag[x]),tag[x]=idx;
            else modify(mid+1,r,x<<1|1,idx);
        }
        else if(k[tag[x]]>k[idx]){ 
        
            if(y1<=y2) modify(mid+1,r,x<<1|1,tag[x]),tag[x]=idx;
            else modify(l,mid,x<<1,idx);
        }
        else if(b[tag[x]]<b[idx]) tag[x]=idx;
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) modify(l,mid,x<<1,idx);
    if(mid<R) modify(mid+1,r,x<<1|1,idx);
}

pii query(int l,int r,int x,int pos){ 
        
    if(l==r){ 
        
        return pii(cal(tag[x],l),tag[x]);
    }
    pii ans=pii(cal(tag[x],pos),tag[x]),res;
    int mid=l+r>>1;
    if(pos<=mid) res=query(l,mid,x<<1,pos);
    else res=query(mid+1,r,x<<1|1,pos);
    if(ans.first>res.first) return ans;
    else if(ans.first<res.first) return res;
    else if(ans.second<res.second) return ans;
    return res;
}


int main(){ 
        
    scanf("%d",&q);
    while(q--){ 
        
        scanf("%d",&op);
        if(op==1){ 
        
            int x0,y0,x1,y1;
            scanf("%d %d %d %d",&x0,&y0,&x1,&y1);
            x0=(x0+lastans-1)%n+1;
            x1=(x1+lastans-1)%n+1;
            y0=(y0+lastans-1)%p+1;
            y1=(y1+lastans-1)%p+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            L=x0,R=x1;
            k[++tot]=(y1-y0)*1.0/(x1-x0);
            b[tot]=1.0*y0-k[tot]*x0;
            //cout<<"!"<<x0<<" "<<x1<<" "<<y0<<" "<<y1<<endl;
            modify(1,40000,1,tot);
        }
        else{ 
        
            int x;
            scanf("%d",&x);
            x=(x+lastans-1)%n+1;
            lastans=query(1,40000,1,x).second;
            printf("%d\n",lastans);
        }
    }
    return 0;
}

题意： 给出一棵 n n n 个节点的树，且每条边存在一个边权，定义两个点的距离为两点之间的边权之和，现在要求支持两种操作：

• 1. 1. 1.选择一条 s s s 到 t t t 的路径，对于路径上的一个点 r r r，若 r r r 与 s s s 的距离是 d i s dis dis，那么在点 r r r 上添加的数字是 a × d i s + b a \times dis + b a×dis+b
• 2. 2. 2.选择一条 s s s 到 t t t 的路径，需要在路径上选一个点，在再这个点中选一个数字，要求数字越小越好

思路：

• 首先发现 a × d i s + b a \times dis + b a×dis+b 这个式子形如一个一次函数，但是显然我们没法在树上套这个式子，我们来分析这个式子： y = a ∗ d i s t ( s , x ) + b y=a *dist(s,x) + b y=a∗dist(s,x)+b 设 w = l c a ( s , t ) w=lca(s,t) w=lca(s,t)，那么 s − > w s->w s−>w 路径上的一次函数为： y = a ∗ ( d i s [ s ] − d i s [ i ] ) + b = − a ∗ d i s [ i ] + a ∗ d i s [ s ] + b y=a * (dis[s]-dis[i])+b=-a*dis[i]+a*dis[s]+b y=a∗(dis[s]−dis[i])+b=−a∗dis[i]+a∗dis[s]+b w − > t w->t w−>t 路径上的一次函数为： y = a ∗ ( d e p [ i ] − d e p [ w ] + d e p [ s ] − d e p [ w ] ) + b = a ∗ d e p [ i ] + a ∗ ( d e p [ s ] − 2 ∗ d e p [ w ] ) + b y=a*(dep[i]-dep[w]+dep[s]-dep[w])+b=a*dep[i]+a*(dep[s]-2*dep[w])+b y=a∗(dep[i]−dep[w]+dep[s]−dep[w])+b=a∗dep[i]+a∗(dep[s]−2∗dep[w])+b 所以我们分别维护参数为 k = − a , b = a ∗ d i s [ s ] + b k=-a,b=a*dis[s]+b k=−a,b=a∗dis[s]+b 与 k = a , b = a ∗ ( d e p [ s ] − 2 ∗ d e p [ w ] ) + b k=a,b=a*(dep[s]-2*dep[w])+b k=a,b=a∗(dep[s]−2∗dep[w])+b 的两个一次函数在指定区间的区间最小值即可

• 之前都是求单点最值，这题要求区间最值，如果我们像之前一样查询，复杂度显然是 O ( n 2 l o g n ) O(n^2logn) O(n2logn) 难以承受。因此我们根据一次函数的单调性，再维护一个 m i [ x ] mi[x] mi[x] 代表当前区间中所有直线与 x = [ l . . r ] x=[l..r] x=[l..r] 相交的最小值，那么每次我们在当前区间或者子区间插入线段，我们显然要用线段的两个端点来更新最值，并且也要和传统线段树一样用子区间的信息更新。

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int head[maxn],to[maxn<<1],nex[maxn<<1],w[maxn<<1],tot=0;
int sz[maxn],dep[maxn],son[maxn],f[maxn];
ll dis[maxn];
int dfn[maxn],top[maxn],ver[maxn],cnt=0;

ll mi[maxn<<2],tag[maxn<<2];
ll k[maxn<<2],b[maxn<<2];
int ktot=0,L,R;
int n,m;

inline void add(int u,int v,int d){ 
        
    to[++tot]=v;
    w[tot]=d;
    nex[tot]=head[u];
    head[u]=tot;
}

void dfs_1(int u,int fa){ 
        
    sz[u]=1;
    for(int i=head[u];i;i=nex[i]){ 
        
        int v=to[i];
        if(v==fa) continue;
        f[v]=u;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w[i];
        dfs_1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}

void dfs_2(int u,int topf){ 
        
    top[u]=topf;
    dfn[u]=++cnt;
    ver[cnt]=u;
    if(son[u]) dfs_2(son[u],topf);
    for(int i=head[u];i;i=nex[i]){ 
        
        int v=to[i];
        if(v==f[u]||v==son[u]) continue;
        dfs_2(v,v);
    } 
}

ll val(int i,ll x){ 
        return k[i]*dis[ver[x]]+b[i];}

void modify(int l,int r,int x,int i){ 
        
    int mid=l+r>>1,lc=x<<1,rc=lc|1;
    if(L<=l&&r<=R){ 
        
        if(l==r){ 
        
            if(val(tag[x],l)>val(i,l)) tag[x]=i,mi[x]=val(i,l);
            return;
        }
        if(val(tag[x],l)<=val(i,l)&&val(tag[x],r)<=val(i,r)) return;
        ll y1=val(tag[x],mid),y2=val(i,mid);
        if(k[tag[x]]>k[i]){ 
        
            if(y1<=y2) modify(mid+1,r,rc,i);
            else modify(l,mid,lc,tag[x]),tag[x]=i;
        }
        else if(k[tag[x]]<k[i]){ 
        
            if(y1<=y2) modify(l,mid,lc,i);
            else modify(mid+1,r,rc,tag[x]),tag[x]=i;
        }
        else if(b[tag[x]]>b[i]) tag[x]=i;
        mi[x]=min(mi[x],min(val(tag[x],l),val(tag[x],r)));
        mi[x]=min(mi[x],min(mi[lc],mi[rc]));
        return;
    }
    if(L<=mid) modify(l,mid,lc,i);
    if(mid<R) modify(mid+1,r,rc,i);
    mi[x]=min(mi[x],min(mi[lc],mi[rc]));
}

ll query(int l,int r,int x){ 
        
    if(L<=l&&r<=R) return mi[x];
    ll res=min(val(tag[x],max(l,L)),val(tag[x],min(r,R)));
    int mid=l+r>>1;
    if(L<=mid) res=min(res,query(l,mid,x<<1));
    if(mid<R) res=min(res,query(mid+1,r,x<<1|1));
    return res;
}

inline int lca(int u,int v){ 
        
    while(top[u]!=top[v]){ 
        
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=f[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}

inline void modify(int u,int w){ 
        
    while(top[u]!=top[w]){ 
        
        L=dfn[top[u]],R=dfn[u];
        modify(1,n,1,ktot);
        u=f[top[u]];
    }
    L=dfn[w],R=dfn[u];
    modify(1,n,1,ktot);
}

inline ll query(int u,int v){ 
        
    ll res=1e18;
    while(top[u]!=top[v]){ 
        
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        L=dfn[top[u]],R=dfn[u];
        res=min(res,query(1,n,1));
        u=f[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    L=dfn[v],R=dfn[u];
    return min(res,query(1,n,1));
}

int main(){ 
        
    b[0]=123456789123456789;
    scanf("%d %d",&n,&m);
    int u,v,d;
    for(int i=1;i<n;i++){ 
        
        scanf("%d %d %d",&u,&v,&d);
        add(u,v,d),add(v,u,d);
    }
    for(int i=1;i<=(n<<2);i++) mi[i]=123456789123456789;
    dfs_1(1,0);
    dfs_2(1,1);
    int op,s,t;
    ll a,c;
    while(m--){ 
        
        scanf("%d %d %d",&op,&s,&t);
        if(op==1){ 
        
            scanf("%lld %lld",&a,&c);
            int w=lca(s,t);
            k[++ktot]=-a,b[ktot]=c+a*dis[s];
            modify(s,w);
            k[++ktot]=a,b[ktot]=a*(dis[s]-2*dis[w])+c;
            modify(t,w);
        }
        else printf("%lld\n",query(s,t));
    }
    return 0;
}