P4097 【模板】李超线段树 / [HEOI2013] Segment 题解

· · 题解

学了几次也是终于写懂李超线段树了，来写一篇模板题题解供初学者理解。

算法介绍

李超线段树是一种支持插入一个定义域为 [l,r] 的一次函数（即线段，一次函数便于理解）以及求与 x=k 相交的所有线段中交点纵坐标最大的线段的编号的数据结构，常用于优化斜率优化的题目。

算法流程

李超线段树的每个区间 [l,r] 上只存了一条线段，并且这个线段的一次函数定义域 [L,R] 包含 [l,r]，意味着这条线段在区间中每一个位置都是合法的。

每次查询的时候我们在线段树上包含 k 的 \log M（M 为值域）个区间取最优解，复杂度 \mathcal{O}(\log M)。

为什么要取 \log M 个区间的最优解呢？这就得提到我们怎么选择保留在区间 [l,r] 上的这一条线段。

首先如果有一条线段严格比另一条更优，即在 l 和 r 处值都严格大于另外一条，那么可以结束递归（另一条不可能成为答案）。

如果没有的话，那么说明两条线段一定有交点，我们取区间中点 mid，在区间 [l,r] 上保留在 mid 处值更大的线段，因为在 mid 处更劣的线段一定在区间的一边是严格劣于另一条的，所以说只需要将这一条递归到另一边的区间，这样就保证了复杂度。然后因为保留在这个区间上的线段是在大部分情况下最优并不是严格最优，所以查询的时候要取最优解。

如果插入直线的话复杂度是 \mathcal{O}(\log M) 的，插入线段的话因为要判断区间和线段的一次函数定义域的包含关系所以复杂度是 \mathcal{O}(\log^2 M) 的。

代码实现

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PDI pair<long double,int>
using namespace std;
const int MAXN = 4e4 + 10;
const int MR = 1e5 + 10;
const int mod1 = 39989;
const int mod2 = 1e9;
const long double eps = 1e-9;
const int inf = 2e9;
int num=0;
struct Line{
    long double k,b;
    int mn,mx;
    long double Get(int x){
        if(x<mn||x>mx) return -inf;
        return k*x+b;
    }
}e[MR];
struct Lichao_Segment_Tree{
    #define ls (x<<1)
    #define rs (x<<1|1)
    int id[MAXN<<2];
    void update(int x,int l,int r,int L,int R,int k){
        if(L<=l&&r<=R){
            if(!id[x]){
                id[x]=k;
                return ;
            }
            int mid=(l+r)>>1;
            if(e[k].Get(mid)-e[id[x]].Get(mid)>eps) swap(id[x],k);
            if(e[k].Get(l)-e[id[x]].Get(l)>eps||(e[k].Get(l)==e[id[x]].Get(l)&&k<id[x])) update(ls,l,mid,L,R,k);
            if(e[k].Get(r)-e[id[x]].Get(r)>eps||(e[k].Get(r)==e[id[x]].Get(r)&&k<id[x])) update(rs,mid+1,r,L,R,k);
            return ;
        }
        int mid=(l+r)>>1;
        if(L<=mid) update(ls,l,mid,L,R,k);
        if(R>mid) update(rs,mid+1,r,L,R,k);
    }
    PDI Cmp(PDI p,PDI q){
        if(p.first==q.first) return (p.second<q.second)?p:q;
        else return (p.first-q.first>eps?p:q);
    }
    PDI query(int x,int l,int r,int p){
        PDI res={-inf,0};
        if(id[x]) res={e[id[x]].Get(p),id[x]};
        if(l==r) return res;
        int mid=(l+r)>>1;
        if(p<=mid) res=Cmp(res,query(ls,l,mid,p));
        else res=Cmp(res,query(rs,mid+1,r,p));
        return res;
    }
}T;
int main(){
    int Q,lastans=0;
    scanf("%d",&Q);
    while(Q--){
        int op,x0,y0,x1,y1,k;
        scanf("%d",&op);
        if(!op){
            scanf("%d",&k);
            k=(k+lastans-1)%mod1+1;
            printf("%d\n",lastans=T.query(1,1,mod1,k).second);
        }
        else{
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            x0=(x0+lastans-1)%mod1+1;
            x1=(x1+lastans-1)%mod1+1;
            y0=(y0+lastans-1)%mod2+1;
            y1=(y1+lastans-1)%mod2+1;
            num++;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            if(x0==x1){
                e[num].k=0,e[num].b=max(y0,y1);
                e[num].mn=e[num].mx=x0;
            }
            else{
                e[num].k=(y1-y0)*1.0/(x1-x0),e[num].b=(y1-e[num].k*x1);
                e[num].mn=x0,e[num].mx=x1;
            }
            T.update(1,1,mod1,e[num].mn,e[num].mx,num);
        }
    }
}