李超线段树

JK_LOVER · 2020-05-13 16:37:38 · 题解

写在前面

如果格式炸了，请前往这里 QwQ 。

李超线段树

引入

查询在平面直角坐标系中与直线 x=x_0 的相交的最大 (最小) 值。换而言之就是查询 \max (k_ix_0+b_i) 的值。

实现

我们发现当我们插入一条线段时，我们只会在直线交点中修改。所以我们将问题转化为 \text{找到每条直线的交点，并修改} 。可以发现这其实就是一个凸壳，这也是李超线段树可以维护并优化一些 dp 方程的原因。我们考虑用线段树来维护每个区间的最大值。

插入

我们发现每次找到一个交点我们就修改它，那么我们还要递归它的儿子，所以每次都是 O(n) ，那么复杂度是不可以接受的。我可以借鉴最短路的 heap 的延迟删除，我们只是将这条线段放在下一层。并不删除它。这里放两种插入方法。


int change(int u,int pre,int l,int r,int now)
{
    if(!u) u = ++tot;
    int mid = l+r>>1;   
    if(!pre)
    {
        t[u] = now;
        return u;
    }
    if(l == r) 
    {
        if(f(l,seg[pre].k,seg[pre].b) <= f(l,seg[now].k,seg[now].b))
        t[u] = now;
        return u;
    }
    double val_mid = f(mid,seg[now].k,seg[now].b);
    double val_Mid = f(mid,seg[pre].k,seg[pre].b);
    if(val_mid >= val_Mid)
    {
        if(seg[now].k >= seg[pre].k) 
        {
            t[u] = now;
            lc[u] = change(lc[u],t[lc[u]],l,mid,pre);
            return u;
        }
        else 
        {
            t[u] = now;
            rc[u] = change(rc[u],t[rc[u]],mid+1,r,pre);
            return u;
        }
    }
    else 
    {
        if(seg[now].k >= seg[pre].k) 
        {
            rc[u] = change(rc[u],t[rc[u]],mid+1,r,now);
            return u;
        }
        else 
        {
            lc[u] = change(lc[u],t[lc[u]],l,mid,now);
            return u;
        }
    }
    return u;
}

以上代码的时间复杂度十分清晰，我们只递归了一边那么复杂度是由树高决定的，为 O(\log n) 。其思想，总结如下：

如果插入的线段的中值大：如果插入的线段斜率大，则交点出现在左侧，向左递归；反之向交点在右侧，因为我们覆盖了这个节点的线段，所以传的参数应该是原线段。
如果插入的线段的中值小：如果插入的线段斜率大，则交点出现在右侧，向右递归；反之向交点在左侧，因为我们 没有覆盖 了这个节点的线段，所以传的参数应该是插入线段。
用图例说明：红色为插入线段，黑色为原先线段。

II:

int insert(int u,int pre,int l,int r,int now)
{
    if(!u) u = ++tot; 
    double val_l = f(l,seg[now].k,seg[now].b);double val_r = f(r,seg[now].k,seg[now].b);
    double val_L = f(l,seg[pre].k,seg[pre].b);double val_R = f(r,seg[pre].k,seg[pre].b);
    if(!pre||(val_r>=val_R&&val_l>=val_L)) 
    {t[u] = now;return u;}
    if(val_R>=val_r&&val_L>=val_l)
    {return u;}
    int mid = l+r>>1;
    lc[u] = insert(lc[u],t[lc[u]],l,mid,now);
    rc[u] = insert(rc[u],t[rc[u]],mid+1,r,now);
    return u;
}

这种方法是来自大佬 @TheShadow 的方法。时间复杂度是等同于单点查询的。虽然我们两边都递归了，但两条直线最多只有一个交点。所以复杂度还是 O(\log n) 。其思想是利用函数的单调性，如果左右端点的值都大(小) ，那么这条直线肯定就没有贡献了，则可以 return 。

查询

因为我们是没有完全删去一条线段的，所以每一条覆盖了这个点的线段都要计算 f(x_0) 。

double query(int u,int l,int r,int p)
{
    if(l==r) return f(l,seg[t[u]].k,seg[t[u]].b);
    double ans = f(p,seg[t[u]].k,seg[t[u]].b);
    int mid = l+r>>1;
    if(p <= mid) return max(ans,query(lc[u],l,mid,p));
    else return max(ans,query(rc[u],mid+1,r,p));
}

总结

李超线段树是一种码量不大的的数据结构，在很多时候用来维护凸壳是十分优秀的工具。

代码

#include<bits/stdc++.h>

using namespace std;

int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f?-x:x;
}

const int maxn = 1e6+10;
const int Maxn = 4e6+10;
int tot=0,root,t[Maxn],lc[Maxn],rc[Maxn];
struct node{double k,b;}seg[Maxn];

double f(int x,double k,double b){return k*x+b;}

int insert(int u,int pre,int l,int r,int now)
{
    if(!u) u = ++tot; 
    double val_l = f(l,seg[now].k,seg[now].b);double val_r = f(r,seg[now].k,seg[now].b);
    double val_L = f(l,seg[pre].k,seg[pre].b);double val_R = f(r,seg[pre].k,seg[pre].b);
    if(!pre||(val_r>=val_R&&val_l>=val_L)) 
    {t[u] = now;return u;}
    if(val_R>=val_r&&val_L>=val_l)
    {return u;}
    int mid = l+r>>1;
    lc[u] = insert(lc[u],t[lc[u]],l,mid,now);
    rc[u] = insert(rc[u],t[rc[u]],mid+1,r,now);
    return u;
}

int change(int u,int pre,int l,int r,int now)
{
    if(!u) u = ++tot;
    int mid = l+r>>1;   
    if(!pre)
    {
        t[u] = now;
        return u;
    }
    if(l == r) 
    {
        if(f(l,seg[pre].k,seg[pre].b) <= f(l,seg[now].k,seg[now].b))
        t[u] = now;
        return u;
    }
    double val_mid = f(mid,seg[now].k,seg[now].b);
    double val_Mid = f(mid,seg[pre].k,seg[pre].b);
    if(val_mid >= val_Mid)
    {
        if(seg[now].k >= seg[pre].k) 
        {
            t[u] = now;
            lc[u] = change(lc[u],t[lc[u]],l,mid,pre);
            return u;
        }
        else 
        {
            t[u] = now;
            rc[u] = change(rc[u],t[rc[u]],mid+1,r,pre);
            return u;
        }
    }
    else 
    {
        if(seg[now].k >= seg[pre].k) 
        {
            rc[u] = change(rc[u],t[rc[u]],mid+1,r,now);
            return u;
        }
        else 
        {
            lc[u] = change(lc[u],t[lc[u]],l,mid,now);
            return u;
        }
    }
    return u;
}

double query(int u,int l,int r,int p)
{
    if(l==r) return f(l,seg[t[u]].k,seg[t[u]].b);
    double ans = f(p,seg[t[u]].k,seg[t[u]].b);
    int mid = l+r>>1;
    if(p <= mid) return max(ans,query(lc[u],l,mid,p));
    else return max(ans,query(rc[u],mid+1,r,p));
}

int cnt = 0;

int main()
{
    int n = read();
    for(int i = 1;i <= n;i++)
    {
        char s[100];
        cin>>s;
        if(s[0] == 'Q') {
            int p=read();
            printf("%d\n",(int)(query(root,1,maxn,p)/100));
        }
        if(s[0] == 'P')
        {
            ++cnt;
            cin>>seg[cnt].b>>seg[cnt].k;
            seg[cnt].b -= seg[cnt].k;
            //root = insert(root,t[root],1,maxn,cnt);
            root = change(root,t[root],1,maxn,cnt);
        }
    }
}