李超线段树

luckydrawbox · 2022-06-05 00:24:28 · 个人记录

宏定义

常量与变量

函数

代码

#define pl p<<1
#define pr p<<1|1
struct Segment_Tree{
    struct Tree{
        int l,r;
        long long k,b;
    }a[N<<2];
    void build(int p,int l,int r){
        a[p].l=l;a[p].r=r;
        a[p].k=0;a[p].b=0;
        if(l==r)
            return;
        int mid=(l+r)>>1;
        build(pl,l,mid);
        build(pr,mid+1,r);
    }
    void change(int p,int l,int r,long long k,long long b){
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=a[p].l&&a[p].r<=r){
            ll x0=a[p].l,x1=a[p].r;
            ll py0=a[p].k*x0+a[p].b,py1=a[p].k*x1+a[p].b,py2=a[p].k*mid+a[p].b;
            ll ny0=k*x0+b,ny1=k*x1+b,ny2=k*mid+b;
            if(ny0>=py0&&ny1>=py1)
                a[p].k=k,a[p].b=b;
            else if(ny0<=py0&&ny1<=py1)
                return;
            else{
                if(ny0>py0){
                    if(ny2<py2)
                        change(pl,l,r,k,b);
                    else{
                        change(pr,l,r,a[p].k,a[p].b);
                        a[p].k=k,a[p].b=b;
                    }
                }
                else{
                    if(ny2>py2){
                        change(pl,l,r,a[p].k,a[p].b);
                        a[p].k=k,a[p].b=b;
                    }
                    else
                        change(pr,l,r,k,b);
                }
            }
            return;
        }
        if(l<=mid)
            change(pl,l,r,k,b);
        if(r>mid)
            change(pr,l,r,k,b);
    }
    long long ask(int p,int x){
        ll ans=x*a[p].k+a[p].b;
        if(a[p].l==a[p].r)
            return ans;
        int mid=(a[p].l+a[p].r)>>1;
        if(x<=mid)
            ans=max(ans,ask(pl,x));
        else
            ans=max(ans,ask(pr,x));
        return ans;
    }
}tree;