算法简述

李超线段树是用于维护一些直线对于x=k交点的最值。

核心思想是中点较优解。

对于一个区间插入一条线段,分为3种情况。

这里拿最大值举例。

  1. 当插入的线段在区间内覆盖当前线段时,直接替代
  2. 当插入的线段被当前线段在区间内完全覆盖时,直接不管
  3. 当插入的线段在当前区间有交点时,当前线段更新成中点更优的线段,次优的根据斜率判断向左还是向右下传。

例题

【CF932F】Escape Through Leaf

题意:

给你一颗有n个点的树 , 每个节点有两个权值a_i,b_i.

u跳到v的代价是a_u*b_v. 你需要计算每个节点跳到叶子的最小代价 .

(n\leq 10^5,−10^5\leq a_i,b_i\leq 10^5)

题解:

很简单可以推出一个树形dp的式子。

f_u=\min(a_u*b_v+f_v)

显然是n^2的,发现很像斜率为b_v,截距为f_vx=a_u的最小值,可以用李超线段树维护。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define int long long
#define ll long long
#define db double
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int ls[Max*60],rs[Max*60],cnt,n,tot,rt[Max],f[Max],head[Max];
struct node
{
    int t,nt;
}e[Max<<1];
il void add(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
struct line
{
    int k,b,id;
}t[Max<<2];
il int calc(line a,int x)
{
    return a.k*x+a.b;
}
il void add(int &x,int l,int r,line p)
{
    if(!x) x=++cnt;
    int mid=(l+r)>>1;
    if(calc(t[x],mid)>calc(p,mid)||(!t[x].id)) swap(t[x],p);
    db crs=1.0*(t[x].b-p.b)/(p.k-t[x].k);
    if(l==r||t[x].k==p.k||crs<l||crs>r||(!p.id)) return;
    if(p.k>t[x].k) add(ls[x],l,mid,p);
    else add(rs[x],mid+1,r,p);
}
il int merge(int x,int y,int l,int r)
{
    if(!x) return y;
    if(!y) return x;
    add(x,l,r,t[y]);
    int mid=(l+r)>>1;
    ls[x]=merge(ls[x],ls[y],l,mid);
    rs[x]=merge(rs[x],rs[y],mid+1,r);
    return x;
}
il line qry(int x,int l,int r,int p)
{
    if(l==r) return t[x];
    int mid=(l+r)>>1;
    line k;
    if(p<=mid) k=qry(ls[x],l,mid,p);
    else k=qry(rs[x],mid+1,r,p);
    return ((!k.id)||calc(k,p)>calc(t[x],p))?t[x]:k;
}
int a[Max],b[Max];
il void ins(int x)
{
    ll k=b[x],b=f[x]-k*Max;
    add(rt[x],1,Max<<1,(line){k,b,x});
}
il int ask(int u)
{
    int v=qry(rt[u],1,Max<<1,a[u]+Max).id;
    return a[u]*b[v]+f[v];
}
il void dfs(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa) continue;
        dfs(v,u);
        rt[u]=merge(rt[u],rt[v],1,Max<<1);
    }
    f[u]=ask(u);
    ins(u);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%lld ",f[i]);
    puts("");
}

还有三题晚上更新