李超线段树

模板

考虑每个区间维护落在当前区间内一条线段

当有一条线段插入时，将新线段与原线段进行比较，若互不相交，保留较靠上的一条

若相交，保留中点较靠上的一条，将另一条线段下放到左/右区间内

因为另一条线段可能在某个小区间内的答案更优

查询则直接从根走到叶子，输出路径上高度最大的线段编号

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long 
#define y1 QwQ
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l+r)>>1)
#define eps (1e-6)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int z7z=39989,Eta=1e9,N=4e4+10;
    int n,x1,y1,x2,y2,id;
    int ret;
    struct node
    {
        double y1,y2;
        int id;
    }ans[N<<2];
    inline void update(int x1,double y1,int x2,double y2,int l,int r,int p,int k)
    {
        if(x1==l&&r==x2)
        {
            if(fabs(ans[p].y1-y1)<eps&&fabs(ans[p].y2-y2)<eps)
            {
                if(!ans[p].id) ans[p].id=k;
                return;
            }
            if(ans[p].y1>=y1&&ans[p].y2>=y2) return;
            if(y1>ans[p].y1&&y2>ans[p].y2)
            {
                ans[p]=(node){y1,y2,k};
                return;
            }
            double t1=(y1+y2)/2.0,t2=(ans[p].y1+ans[p].y2)/2.0;
            if(t1>t2)
            {
                if(l==r)
                {
                    ans[p]=(node){y1,y2,k};
                    return;
                }
                if(ans[p].y1>=y1)
                {
                    double t=1.0*(ans[p].y2-ans[p].y1)/(r-l);
                    t=ans[p].y1+t*(mid-l);
                    update(l,ans[p].y1,mid,t,l,mid,ls(p),ans[p].id);
                }
                else
                {
                    double t=1.0*(ans[p].y2-ans[p].y1)/(r-l);
                    t=ans[p].y1+t*(mid-l+1);
                    update(mid+1,t,r,ans[p].y2,mid+1,r,rs(p),ans[p].id);
                }
                ans[p]=(node){y1,y2,k};
            }
            else
            {
                if(l==r) return;
                if(y1>=ans[p].y1)
                {
                    double t=1.0*(y2-y1)/(r-l);
                    t=y1+t*(mid-l);
                    update(l,y1,mid,t,l,mid,ls(p),k);
                }
                else
                {
                    double t=1.0*(y2-y1)/(r-l);
                    t=y1+t*(mid-l+1);
                    update(mid+1,t,r,y2,mid+1,r,rs(p),k);
                }
            }
            return;
        }
        if(x2<=mid) update(x1,y1,x2,y2,l,mid,ls(p),k);
        else if(x1>mid) update(x1,y1,x2,y2,mid+1,r,rs(p),k);
        else
        {
            double t=1.0*(y2-y1)/(x2-x1);
            update(x1,y1,mid,y1+t*(mid-x1),l,mid,ls(p),k);
            update(mid+1,y1+t*(mid-x1+1),x2,y2,mid+1,r,rs(p),k);
        }
    }
    inline node query(int pos,int l,int r,int p)
    {
        if(l==r) return (node){max(ans[p].y1,ans[p].y2),0,ans[p].id};
        double t=1.0*(ans[p].y2-ans[p].y1)/(r-l);
        t=ans[p].y1+t*(pos-l);
        node son;
        if(pos<=mid) son=query(pos,l,mid,ls(p));
        else son=query(pos,mid+1,r,rs(p));
        if(t==son.y1) return (node){t,0,min(ans[p].id,son.id)};
        else if(t>son.y1) return (node){t,0,ans[p].id};
        else return son;
    }
    inline void main()
    {
        n=read();
        for(int opt,k,i=1;i<=n;++i)
        {
            opt=read();
            if(!opt)
            {
                k=read();
                k=(k+ret-1)%z7z+1;
                printf("%d\n",ret=query(k,1,z7z,1).id);
            }
            else
            {
                x1=read(),y1=read(),x2=read(),y2=read();
                x1=(x1+ret-1)%z7z+1;x2=(x2+ret-1)%z7z+1;
                y1=(y1+ret-1)%Eta+1;y2=(y2+ret-1)%Eta+1;
                if(x1>x2) swap(x1,x2),swap(y1,y2);
                if(x1==x2) y1=y2=max(y1,y2);
                update(x1,y1,x2,y2,1,z7z,1,++id);
            }
        }
    }
}
signed main()
{
    red::main();
    return 0;
}
/*
3
1 3 5 7 7
1 3 9 7 3
0 5 

*/

李超线段树

原文：https://www.cnblogs.com/knife-rose/p/12263623.html