#edu2008. 李超线段树

李超线段树

问题引入

要求在平面直角坐标系下，在线维护两个操作：

  1. 在平面上加入一条线段
  2. 给定一个数 kk, 询问与直线 x=kx=k 相交的线段的交点的纵坐标最值。

李超线段树就是用于维护平面直角坐标系内线段关系的树。

李超线段树每个节点存储对应区间 [l,r][l,r] 上最优线段信息(编号) ，实际上是懒标记（不一定是最优的），从这个角度理解，李超线段树实际是一种基于标记永久化的线段树。

标记永久化就是指修改时一路更改被影响到的节点，询问时则一路累加路上的标记，从而省去标记上传下传的操作。

插入线段操作

线段树下标是横坐标，维护每个区间的中点处最高/最低的线段（最优线段）

设当前区间为 [l,r][l,r] ,新线段的横坐标的范围为 [L,R][L,R] 。

  1. 如果新线段完全覆盖了 [l,r][l,r] , 即 L≤l≤r≤RL \le l \le r \le R , 此时维护区间的最优线段。 (1).如果新线段在中点处的 YY 值大于(优于)旧线段在中点处的 YY 值，那么交换新旧线段编号，这样做一箭双雕： 新线段的编号存入了当前区间标记 t[p]t[p] ,同时 idid 指向旧线段。执行完这一步，线段树当前节点存入了最优线段，接下来讨论递归左区间还是右区间。 (2).如果 x=lx=l 处，idid 线段优于 t[p]t[p] 线段，那递归左侧一半区间。 (3).如果 x=rx=r 处，idid 线段优于 t[p]t[p] 线段，那递归右侧一半区间。

    情况(2)、(3)至多有一个满足，这种情况递归深度是 O(log⁡n)O(\log{n}) ，由于一段区间对应线段树上 O(log⁡n)O(\log{n}) 段，每段递归 O(log⁡n)O(\log{n}) ,那么插入一次线段复杂度就是 O(log⁡2n)O(\log^2{n}) .

  2. 如果新线段伸入了左区间 [l,mid][l,mid] 即 L≤midL\le mid,则递归左区间;

  3. 如果新线段伸入了右区间 [mid+1,r][mid+1,r] ,则递归右区间;

核心代码：

void insert(int p,int l,int r,int L,int R,int id)
{
    int mid=l+r>>1;
    if(L<=l && r<=R)
    {
        if(Y(id,mid)>Y(t[p],mid))swap(t[p],id);   //线段树上保留 最优线段 即：中点处最优

        if(Y(id,l)>Y(t[p],l))insert(p<<1,l,mid,L,R,id);   //左侧 id更优 继续递归左侧
        if(Y(id,r)>Y(t[p],r))insert(p<<1|1,mid+1,r,L,R,id); //右侧 id更优 继续递归右侧

        return;
    }
    if(L<=mid)insert(p<<1,l,mid,L,R,id);
    if(mid<R)insert(p<<1|1,mid+1,r,L,R,id);
}

询问操作

对于所有包含横坐标 xx 的区间上的最优线段计算 Y 值，保留最大/最小 ，单次询问复杂度就是 O(log⁡n)O(\log{n})。

核心代码：

double query(int p,int l,int r,int x)
{
    if(l==r)return Y(t[p],x);
    int mid=l+r>>1;
    double ret=Y(t[p],x);
    if(x<=mid)return max(ret,query(p<<1,l,mid,x));
    else return max(query(p<<1|1,mid+1,r,x),ret);
}

综上，李超线段树时间复杂度是 O(mlog⁡2n)O(m\log^2{n}) ,其中 m 是插入线段次数，nn 是横坐标区间长度。

例1：P4254[JSOI2008] Blue Mary 开公司

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5;
struct Line{
    double k,b;   //k是斜率 b是截距
}line[N+10];
int n,cnt;
int t[N*4+10];  //线段树 保留区间最优线段编号
double Y(int id,int x)
{
    return line[id].k*x+line[id].b;
}
void insert(int p,int l,int r,int L,int R,int id)
{
    int mid=l+r>>1;
    if(L<=l && r<=R)
    {
        if(Y(id,mid)>Y(t[p],mid))swap(t[p],id);   //线段树上保留 最优线段 即：中点处最优

        if(Y(id,l)>Y(t[p],l))insert(p<<1,l,mid,L,R,id);   //左侧 id更优 继续递归左侧
        if(Y(id,r)>Y(t[p],r))insert(p<<1|1,mid+1,r,L,R,id); //右侧 id更优 继续递归右侧

        return;
    }
    if(L<=mid)insert(p<<1,l,mid,L,R,id);
    if(mid<R)insert(p<<1|1,mid+1,r,L,R,id);
}
double query(int p,int l,int r,int x)
{
    if(l==r)return Y(t[p],x);
    int mid=l+r>>1;
    double ret=Y(t[p],x);
    if(x<=mid)ret=max(ret,query(p<<1,l,mid,x));
    else ret=max(query(p<<1|1,mid+1,r,x),ret);
    return ret;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    while(n--)
    {
        string op;
        cin>>op;
        if(op[0]=='Q')  //查询
        {
            int t;
            cin>>t;
            int ans=query(1,1,N,t)/100;
            cout<<ans<<"\n";
        }
        else     //插入线段
        {
            double s,p;
            cin>>s>>p;
            line[++cnt]={p,s-p};   //斜率是p 截距 s-p
            insert(1,1,N,1,N,cnt);   //插入线段
        }
    }
    
    return 0;
}

例2：Luogu P4097 【模板】李超线段树 / [HEOI2013] Segment

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> pdi;   //将最优的y 和 对应线段编号id 打包保存
const int N=1e5+10,Mx=39989,My=1e9;
const double eps=1e-9;
struct Line{
    double k,b;
}line[N];
int n,cnt;
int t[N*4];  //线段树中需要保留 最优线段编号
double Y(int id,int x)
{
    return line[id].k*x+line[id].b;
}
int cmp(double x,double y)
{
    if(x-y>eps)return 1;
    if(y-x>eps)return -1;
    return 0;
}
pdi mx(pdi a,pdi b)
{
    if(cmp(a.first,b.first)==0)return a.second<b.second? a :b;
    if(cmp(a.first,b.first)>0)return a;
    else return b;
}

pdi query(int p,int l,int r,int x)
{
    if(l==r)return {Y(t[p],x),t[p]};
    pdi ret={Y(t[p],x),t[p]};
    int mid=l+r>>1;
    if(x<=mid)return mx(ret,query(p<<1,l,mid,x));
    else return mx(ret,query(p<<1|1,mid+1,r,x));
}

void insert(int p,int l,int r,int L,int R,int id)
{
    int mid=l+r>>1;
    if(L<=l && r<=R)
    {
        int cm=cmp(Y(id,mid),Y(t[p],mid));
        if(cm==1 || (cm==0 && id<t[p]))swap(id,t[p]);   //存最优线段编号
        
        int cl=cmp(Y(id,l),Y(t[p],l));
        if(cl==1 || (cl==0 && id<t[p]))insert(p<<1,l,mid,L,R,id);
        
        int cr=cmp(Y(id,r),Y(t[p],r));
        if(cr==1 ||(cr==0 && id<t[p]))insert(p<<1|1,mid+1,r,L,R,id);
        
        return;
    }
    if(L<=mid)insert(p<<1,l,mid,L,R,id);
    if(mid<R)insert(p<<1|1,mid+1,r,L,R,id);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    int op,k,x0,y0,x1,y1,lastans=0;
    while(n--)
    {
        cin>>op;
        if(op==0)  //查询最优解
        {
            cin>>k;
            int x=(k+lastans-1)%Mx+1;
            pdi ans=query(1,1,Mx,x);   //返回最优线段 y 值和对应编号
            cout<<ans.second<<"\n";
            lastans=ans.second;
        }
        else     //插入线段
        {
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1)%Mx+1;
            x1=(x1+lastans-1)%Mx+1;
            y0=(y0+lastans-1)%My+1;
            y1=(y1+lastans-1)%My+1;
            if(x0>x1)swap(x0,x1),swap(y0,y1);

            double k,b;
            //特判 斜率不存在的线段
            if(x0==x1)k=0,b=max(y0,y1);  //当作一个点处理
            else
            {
                k=(y1-y0)*1.0/(x1-x0);
                b=y0-k*x0;
            }
            line[++cnt]={k,b};
            insert(1,1,Mx,x0,x1,cnt);  //插入线段
        }
    }
    
    
    return 0;
}

李超线段树解决斜率优化问题

对于斜率优化问题（完整斜率优化问题请参考斜率优化教程） y(j)=k(i)∗x(j)+b(i)y(j)=k(i)*x(j)+b(i) 中，当 x(j)x(j) 不单调，需要动态维护凸壳，实际上所有斜率优化问题都可以用李超线段树快速求出最优决策点，当然复杂度可能会大一点，是 O(nlog⁡2n)O(n\log^2{n})。

例3 [CEOI2017]Building Bridges

题目描述

有 nn 根柱子依次排列，每根柱子都有一个高度。第 ii 根柱子的高度为 hih_i​。

现在想要建造若干座桥，如果一座桥架在第 ii 根柱子和第 jj 根柱子之间，那么需要 (hi​−hj​)2(h_i​−h_j​)^2​​ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 ii 根柱子被拆除的代价为 wi​w_i​，注意 wiw_i​ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 11 根柱子和第 nn 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

数据范围

2≤n≤105,0≤hi​,∣wi​∣≤1062 \le n \le 10^5,0 \le h_i​,|w_i​| \le 10^6

分析:

定义 fif_i 表示前 ii 根柱子连接的最小代价。

fi=min⁡{fj+(hi−hj)2+sum[i−1]−sum[j]}f_i=\min{ \{f_j+(h_i-h_j)^2+sum[i-1]-sum[j]} \}

如果考虑斜率优化，ii 是定值, jj 是变量，化简式子得到：

fj=(2hi)∗hj−hj2−sum[j]+fi−hi2+sum[i−1]f_j=(2h_i)*h_j-h_j^2-sum[j]+f_i-h_i^2+sum[i-1]

发现 x(j)=hjx(j)=h_j 不单调，斜率 2∗hi2*h_i 也不单调，转化为李超线段树优化。

转化式子为：

fi−hi2−sum[i−1]=(−2∗hj)∗hi+fj−sum[j]+hj2f_i-h_i^2-sum[i-1]=(-2*h_j)*h_i+f_j-sum[j]+h_j^2

问题转换为：每次插入直线 y=−2hj∗x+fj+hj2−sum[j]y=-2h_j*x+f_j+h_j^2-sum[j] ，求在 x=h[i]x=h[i] 时的最小值。

用李超线段树维护即可，时间复杂度是 O(nlog⁡2n)O(n\log^2{n})

参考代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=1e5+10, M=1e6;
struct Line{
    ll k,b;
}line[N];
int n,cnt,t[M*4+10];  //t是线段树
ll f[N],sum[N],h[N];
ll Y(int id,int x)
{
    return line[id].k*x+line[id].b;
}
void insert(int p,int l,int r,int L,int R,int id)
{
    int mid=l+r>>1;
    if(L<=l && r<=R)
    {
        if(Y(id,mid)<Y(t[p],mid))swap(t[p],id);   //线段树上保留 最优线段 即：中点处最优

        if(Y(id,l)<Y(t[p],l))insert(p<<1,l,mid,L,R,id);   //左侧 id更优 继续递归左侧
        if(Y(id,r)<Y(t[p],r))insert(p<<1|1,mid+1,r,L,R,id); //右侧 id更优 继续递归右侧

        return;
    }
    if(L<=mid)insert(p<<1,l,mid,L,R,id);
    if(mid<R)insert(p<<1|1,mid+1,r,L,R,id);
}
ll query(int p,int l,int r,int x)
{
    if(l==r)return Y(t[p],x);
    int mid=l+r>>1;
    ll ret=Y(t[p],x);
    if(x<=mid)return min(ret,query(p<<1,l,mid,x));
    else return min(query(p<<1|1,mid+1,r,x),ret);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)
    {
        int w;
        cin>>w;
        sum[i]=sum[i-1]+w;
    }
    line[0].b=1e18;
    cnt=1;
    line[cnt].k = -2*h[1];
    line[cnt].b  = f[1]-sum[1]+h[1]*h[1];
    insert(1,1,M,1,M,1);
    for(int i=2;i<=n;i++)
    {
        f[i]=h[i]*h[i]+sum[i-1]+query(1,1,M,h[i]);
        ll k=-2*h[i],b=f[i]-sum[i]+h[i]*h[i];
        line[++cnt]={k,b};
        insert(1,1,M,1,M,cnt);
    }
    cout<<f[n];
    
    return 0;
}

其他题目

  1. P4069 [SDOI2016] 游戏 （树链剖分+李超线段树）
  2. 「CF932F」Escape Through Leaf （李超线段树合并）

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 38ms
  4. Powered by Hydro v4.13.3 Modified by byx QQ465039728
  5. 陕ICP备2023000766号