李超线段树总结

写在前面：

最近很久没有发文章了，但是写了还是很多，大概有10+篇草稿。主要是没大有时间找/做例题。以后打算少放一些例题，以后有时间做了后再放在后面。

正文

用一道例题来引入。

Description

要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数n，表示共n 个操作。

接下来n行，每行第一个数为0或1。

若该数为 0，则后面跟着一个正整数 k，表示询问与直线x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。

若该数为 1，则后面跟着四个正整数 x0, y0, x1, y1，表示插入一条两个端点为((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。

其中lastans为上一次询问的答案。初始时lastans=0。

Output

对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。

Sample Input

6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5

Sample Output

2
0 3

HINT

对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

题意：在坐标轴里插入一堆线段，每次给出k，查询x=k这条直线上最上面的一条直线。

如何用线段树解决这个问题呢？我们先把坐标轴用线段树维护一下，每个节点代表一个区间。每个节点的标记里记下经过这个节点的一次函数(k和b的值)。

这样子插入直线就可以把直线的定义域分成logn个区间，每个区间里记一下直线。每次要查询的时候就先找到最下面的子节点，一路找到根节点，统计下最高的就可以了。

但是插入的时候出现冲突了怎么办？

红色代表区间的大小，橙色是mid，黑色是原直线，蓝色是插入直线。

这样的话我们发现黑色直线在左边的区间就没有任何存在的必要了，因为蓝色直线是完全覆盖掉黑色直线的。这样的话我们就可以在这个节点只保留蓝色的直线，然后开始用右半边的黑色直线来更新下面的区间。

这就是一个李超树的实现过程。标记永久化，直到插入的时候才更新标记。

给个代码

#include <cstdio>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define p1 39989
#define p2 1000000000
using namespace std;
struct lines
{
    double k,b;
    int id;
}tree[50010<<2];
lines add_line(int x1,int y1,int x2,int y2,int id)
{
    lines ans;
    ans.id=id;
    if (x1==x2)
        ans.k=0,ans.b=max(y1,y2);
    else
        ans.k=(double)(y2-y1)/(x2-x1),
        ans.b=(double)(y1-ans.k*x1);
    return ans;
}
double get_y(lines p,double x)
{
    return (double)p.k*x+p.b;
}
bool cmp(lines a,lines b,double x)
{
    if (!a.id) return 1;
    if (get_y(a,x)==get_y(b,x))
        return a.id<b.id;
    else
        return get_y(a,x)<get_y(b,x);
}
void add(int rt,int l,int r,lines x)
{
    if (!tree[rt].id)
    {
        tree[rt]=x;
        //return;
    }
    if (cmp(tree[rt],x,l))
        swap(tree[rt],x);
    if (l==r || tree[rt].k==x.k) return;
    int mid=l+r>>1;
    double p=(tree[rt].b-x.b)/(x.k-tree[rt].k);
    if (p<l || p>r) return;
    if (p<=mid) add(lson,tree[rt]),tree[rt]=x;
    else add(rson,x);
}
void insert(int rt,int l,int r,int L,int R,lines x)
{
    if (l>=L && r<=R)
        add(rt,l,r,x);
    else
    {
        int mid=l+r>>1;
        if (L<=mid)
            insert(lson,L,R,x);
        if (R>mid)
            insert(rson,L,R,x);
    }
}
lines query(int rt,int l,int r,int pos)
{
    if (l==r)
        return tree[rt];
    int mid=l+r>>1;lines temp;
    if (pos<=mid)
        temp=query(lson,pos);
    else
        temp=query(rson,pos);
    if (cmp(temp,tree[rt],pos))
        return tree[rt];
    return temp;
}
int N=50000,n,cnt=0,lans=0,com,x0,x1,y0,y1,x;
main()
{
//  freopen("input.txt","r",stdin);
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&com);
        if (com)
        {
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            x0=(x0+lans-1)%p1+1;y0=(y0+lans-1)%p2+1;
            x1=(x1+lans-1)%p1+1;y1=(y1+lans-1)%p2+1;
            if (x0>x1) swap(x0,x1),swap(y0,y1);
            insert(1,1,N,x0,x1,add_line(x0,y0,x1,y1,++cnt));
        }
        else
        {
            scanf("%d",&x);
            x=(x+lans-1)%p1+1; lans=query(1,1,N,x).id;
            printf("%d\n",lans);
        }
    }
}

例题

BZOJ3938
BZOJ4515