李超线段树略解

李超线段树实际就是线段树（废话）

每个节点维护一个永久化的标记（这里只是一定程度上的永久化但还是要下传的）

让线段树中的一个节点只对应一条直线，那么如果在这个区间加入一条直线怎么办呢？要分类讨论，设新加入的f1(x)=k1x+b1，原来的f2(x)=k2x+b2，左端点为l，右端点为r，那么有：

1.f1(d[l])<f2(d[l])且f1(d[r])<f2(d[r])，对应一条直线在两个端点都比另一条小，那么显然在l~r中f1(x)处处比f2(x)小，直接把f2(x)替换为f1(x)；

2.同理若上式的两个符号都为>，那么f1(x)处处不如f2(x)优，不做更改。

3.k1<k2，那么由于不满足1.2，显然两条直线有交点，此时解不等式f1(x)<f2(x)得到x>(b1-b2)/(k2-k1)，那么判断(b1-b2)/(k2-k1)在左半区间还是右半区间递归下传即可；

4.k1>k2同理。

时间复杂度为\(O(n\log^2n)\)

例题（Luogu P4254 [JSOI2008]Blue Mary开公司）

这实际就是模板题（把每种方案转化成线段）

#include <bits/stdc++.h>
#define N 50005
#define db double
using namespace std;
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
inline db Max(register db a,register db b)
{
    return a>b?a:b;
}
int n,m;
struct node{
    db k,b;
    int id;
    inline db getv(register int x)
    {
        return k*x+b;
    }
};
inline bool cmp(register node a,register node b,register int x)
{
    if(!a.id)
        return 1;
    return a.getv(x)!=b.getv(x)?a.getv(x)<b.getv(x):a.id<b.id;
}
node tr[N<<2];
inline void insert(register int x,register int l,register int r,register node v)
{
    if(!tr[x].id)
        tr[x]=v;
    if(cmp(tr[x],v,l))
        swap(tr[x],v);
    if(l==r||tr[x].k==v.k)
        return;
    int mid=l+r>>1;
    db X=(tr[x].b-v.b)/(v.k-tr[x].k);
    if(X<l||X>r)
        return;
    if(X<=mid)
        insert(x<<1,l,mid,tr[x]),tr[x]=v;
    else
        insert(x<<1|1,mid+1,r,v); 
}
inline void Insert(register int x,register int l,register int r,register int L,register int R,register node v)
{
    if(L<=l&&r<=R)
    {
        insert(x,l,r,v);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid)
        Insert(x<<1,l,mid,L,R,v);
    if(R>mid)
        Insert(x<<1|1,mid+1,r,L,R,v);
}
inline node query(register int x,register int l,register int r,register int pos)
{
    if(l==r)
        return tr[x];
    int mid=l+r>>1;
    node tmp;
    if(pos<=mid)
        tmp=query(x<<1,l,mid,pos);
    else
        tmp=query(x<<1|1,mid+1,r,pos);
    return cmp(tr[x],tmp,pos)?tmp:tr[x];
}
int main()
{
    m=read(),n=50000;
    char opt[15];
    while(m--)
    {
        scanf("%s",opt);
        if(opt[0]=='P')
        {
            db k,b;
            scanf("%lf%lf",&k,&b);
            node tmp;
            tmp.k=b,tmp.b=k-b,tmp.id=1;
            Insert(1,1,n,1,n,tmp);
        }
        else
        {
            int x=read();
            printf("%lld\n",(long long)(query(1,1,n,x).getv(x)/100+1e-8));
        }
    }
    return 0;
}

相关习题

1.Luogu P4097 [HEOI2013]Segment

题解

2.Luogu P4069 [SDOI2016]游戏

题解

李超线段树略解

原文：https://www.cnblogs.com/yzhang-rp-inf/p/10349117.html