李超树浅谈

李超树是一个可以多个分段一次函数，并取某个端点上所有一次分段函数的最值。基本李超树需要维护两个操作：

• 在 \([l,r]\) 加入一条线段。
• 询问在 \(k\) 处的最值。

李超树中，每个节点我们存储的函数编号为在这个节点代表区间中点取得最值的函数编号。

插入时，我们首先向线段树一样找到 \([l,r]\) 这个区间，如果这个区间以前的最优线段在中点处没有我们新加入的函数优，我们就交换两个线段编号，把原先在这个区间的线段继续向下递归插入。

继续向下递归插入是这个函数有可能在左右半个区间中的一个中更优，我们可以通过分类讨论来往下递归。

我们查询最值时，只要查询这个路径上所有的线段在这个点取得的值，取 \(\max\) 即可。

关于复杂度，查询显然是 \(O(\log n)\) 的，而对于插入，\([l,r]\) 一共被拆成 \(O(\log n)\) 个区间，向下查又是一个 \(\log\)，所以复杂度应该是 \(\log^2 n\)。

下面的代码为动态开点写法。

代码：

struct Node{
    int ls,rs,mx,mi;
}p[N];
int tot;
inline LCT(){tot=0;}
inline void ChangeMin(int &k,int l,int r,int z,int y,int id){
    if(!k){k=++tot;assert(tot<=N-1);}
    if(l==r){if(!p[k].mi||F(p[k].mi,l)>F(id,l)) p[k].mi=id;return;}int mid=(l+r)>>1;
    if(z<=l&&r<=y){
        if(!p[k].mi) p[k].mi=id;
        if(F(p[k].mi,mid)>F(id,mid)) swap(p[k].mi,id);
        (F(id,l)<F(p[k].mi,l))?ChangeMin(ls(k),l,mid,z,y,id):ChangeMin(rs(k),mid+1,r,z,y,id);
        return;
    }
    if(z<=mid) ChangeMin(ls(k),l,mid,z,y,id);if(mid<y) ChangeMin(rs(k),mid+1,r,z,y,id);
}
inline void ChangeMax(int &k,int l,int r,int z,int y,int id){
    if(!k){k=++tot;}
    if(l==r){if(!p[k].mx||F(p[k].mx,l)<F(id,l)) p[k].mx=id;return;}int mid=(l+r)>>1;
    if(z<=l&&r<=y){
        if(!p[k].mx) p[k].mx=id;
        if(F(p[k].mx,mid)<F(id,mid)) swap(p[k].mx,id);
        (F(id,l)>F(p[k].mx,l))?ChangeMax(ls(k),l,mid,z,y,id):ChangeMax(rs(k),mid+1,r,z,y,id);
        return;
    }
    if(z<=mid) ChangeMax(ls(k),l,mid,z,y,id);if(mid<y) ChangeMax(rs(k),mid+1,r,z,y,id);
}
inline void Change(int &k,int l,int r,int z,int y,int id){
    ChangeMin(k,l,r,z,y,id);ChangeMax(k,l,r,z,y,id);
}
inline int AskMin(int k,int l,int r,int w){
    if(!k) return 0;if(l==r) return p[k].mi;
    int mid=(l+r)>>1;int id=-1;
    if(w<=mid) id=AskMin(ls(k),l,mid,w);else id=AskMin(rs(k),mid+1,r,w);
    if(id==0) return p[k].mi;
    return (F(id,w)<F(p[k].mi,w))?id:p[k].mi;
}
inline int AskMax(int k,int l,int r,int w){
    if(!k) return 0;if(l==r) return p[k].mx;
    int mid=(l+r)>>1;int id=-1;
    if(w<=mid) id=AskMax(ls(k),l,mid,w);else id=AskMax(rs(k),mid+1,r,w);
    if(id==0) return p[k].mx;
    return (F(id,w)>F(p[k].mx,w))?id:p[k].mx;
}
inline void Clear(){mset(p,0);rt=0;tot=0;}