广义李超线段树

struct LCT
{
    int tot=0,rt=0;
    struct Tree{int lc,rc,id;}tr[M];
    ll Ans(ll z,ll x){return p[z].k*x+p[z].b;}
    #define ls (tr[p].lc)
    #define rs (tr[p].rc)
    #define mi ((l+r)>>1)
    void Upd(int &p,int l,int r,int u)
    {
        if(!p)p=++tot;
        int &v=tr[p].id;
        if(Ans(u,mi)>Ans(v,mi))swap(u,v);
        if(Ans(u,l)>Ans(v,l))Upd(ls,l,mi,u);
        if(Ans(u,r)>Ans(v,r))Upd(rs,mi+1,r,u);
    }
    ll Ask(ll p,ll l,ll r,ll d)
    {
        if(!p)return 0;
        ll ans=Ans(tr[p].id,d);
        if(l==r)return ans;
        return max(ans,d<=mi?Ask(ls,l,mi,d):Ask(rs,mi+1,r,d));
    }
    void Clear(int l,int r)
    {
        for(int i=1;i<=tot;i++)tr[i].lc=tr[i].rc=tr[i].id=0;
        tot=rt=0;
        for(int i=l;i<=r;i++)Upd(rt,0,n,i);
    }
}T[M];