李超线段树简要

spdarkle · 2023-12-26 17:21:34 · 个人记录

d0d389d6-b769-451f-84e0-06c0e32439c4

李超线段树简要

功能：

1. 插入一条线段 (x_1,y_1)\to (x_2,y_2)，要求 x_1,x_2 是整数。

2. 查询对于直线 x=k，所交直线所得解 y_{\max/\min}

先给出一份板子，这里推荐打动态开点。

思想：对于每个子区间 [l,r]，维护一条线段满足覆盖了 [l,r]，并且最优。（这个最优定义为不存在一条线段覆盖 [l,r] 的线段全面优于这条线段）。

插入：先利用线段树找到完全覆盖区间，然后我们考虑插入：

当插入线段完全优于当前线段，替换并且 return 。由于一次函数单调性，显然判断两个端点值即可。

完全劣于也直接退出。

否则两边递归——画图分析容易得到在两个子区间至少有一个会完全优于/劣于，不会继续递归。

注意特判 k=\infty 的情况

查询：一查到底，所有路过线段都有可能是答案。

李超线段树动态开点空间复杂度 O(n)

#include<bits/stdc++.h>
using namespace std;
#define N 3005050
#define db double
struct node{
    db k,b;
    void init(db _k,db x,db y){
        k=_k,b=y-x*_k;
    }
    db get(db pos){
        return k*pos+b;
    }
    bool cmp(node &a,db pos){
        return get(pos)<a.get(pos);
    }
};
#define pr pair<int,int>
#define mk make_pair
vector<pr >e[N];//every robit's time and ver
namespace mx{
    node s[N];
    int lc[N],rc[N],num,rt;
    void insert(int &x,int l,int r,int L,int R,node k){
        int mid=l+r>>1;
        if(!x)x=++num,s[x]=(node){-1e9,-1e9};
        if(L<=l&&r<=R){
            bool p=s[x].cmp(k,l),q=s[x].cmp(k,r);
            if(p^q){
                insert(lc[x],l,mid,L,R,k);insert(rc[x],mid+1,r,L,R,k);return ;
            } 
            if(p)s[x]=k;
            return ;
        }
        if(L<=mid)insert(lc[x],l,mid,L,R,k);
        if(mid<R)insert(rc[x],mid+1,r,L,R,k);
    }   
    node find(int x,int l,int r,int pos){
        if(!x)return {-1e9,-1e9};
        if(l==r)return s[x];
        int mid=l+r>>1;node res;
        if(pos<=mid)res=find(lc[x],l,mid,pos);
        else res=find(rc[x],mid+1,r,pos);
        if(s[x].cmp(res,pos))return res;
        return s[x];
    }
}
namespace mn{
    node s[N];
    int lc[N],rc[N],num,rt;
    void insert(int &x,int l,int r,int L,int R,node k){
        int mid=l+r>>1;
        if(!x)x=++num,s[x]=(node){1e9,1e9};
        if(L<=l&&r<=R){
            bool p=s[x].cmp(k,l),q=s[x].cmp(k,r);
            if(p^q){
                insert(lc[x],l,mid,L,R,k);insert(rc[x],mid+1,r,L,R,k);return ;
            } 
            if(!p)s[x]=k;
            return ;
        }
        if(L<=mid)insert(lc[x],l,mid,L,R,k);
        if(mid<R)insert(rc[x],mid+1,r,L,R,k);
    }   
    node find(int x,int l,int r,int pos){
        if(!x)return {1e9,1e9};
        if(l==r)return s[x];
        int mid=l+r>>1;node res;
        if(pos<=mid)res=find(lc[x],l,mid,pos);
        else res=find(rc[x],mid+1,r,pos);
        if(s[x].cmp(res,pos))return s[x];
        return res;
    }
}

插入线段 O(\log^2 n)，插入直线 O(\log n)

运用：

• 李超线段树不支持删除，但支持撤销，具体实现类似于用单调栈存下当前区间的线段，再存下每条线段影响位置，撤销的时候回退即可，类似可持久化并查集。

  这个思路告诉我们可以线段树分治，CDQ分治等手段维护每条线段仅在若干时间段出现的问题。也即删除的问题。多了个 \log n

• 李超线段树维护斜率优化DP

  将DP方程整理为一次函数形式 f_i=k_0A(i)+B(j)，然后维护这条线段即可。

  注意到维护直线，故总复杂度 O(\log n)。推荐动态开点，注意处理负数。

  有时候可能会涉及到 j 的转移范围有多重限制，这时候考虑CDQ，线段树分治，树套树等消去限制。如 jump mission

• 李超线段树合并

  CF932F

  合并方式：合并树 S 到 T 上。

  枚举 S 中每一条线段，直接插入到 T 对应位置对应节点进行更新。复杂度 O(c\log n)，其中 c 为线段总数。

  正确性显然，考虑到每一次插入至少会使得一条线段的深度加一。那么一共 \log n 层，也即每条线段最多插入 O(\log n) 次，均摊复杂度正确。证毕。

  另一种想法：考虑启发式合并。当然两种一起用也没关系。

      int merge(int l,int r,int o,int oo){
          if (!oo) return o;
          if (!o){
              o=newnode();
              k[o]=k[oo],b[o]=b[oo],lson[o]=lson[oo],rson[o]=rson[oo];
              pop(oo);//回收
              return o;
          }
          if (l!=r){
              int mid=l+r>>1;
              lson[o]=merge(l,mid,lson[o],lson[oo]);
              rson[o]=merge(mid+1,r,rson[o],rson[oo]);
          }
          o=add(o,l,r,k[oo],b[oo]);//暴力插入
          pop(oo);
          return o;
      }