李超樹是一個可以多個分段一次函數，并取某個端點上所有一次分段函數的最值?；纠畛瑯湫枰S護兩個操作：

• 在 \([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;}