李超线段树

功能

李超线段树资瓷以下两种操作:

1.在二维平面内插入一条线段
2.询问与直线\(x=k\)相交的线段中，交点纵坐标最大为多少。

原理

结点

李超线段树的每个节点，都维护这一个优势线段。这个优势线段使得该节点所维护区间的中点在该优势线段上最大。

修改

考虑如何维护上面的结点呢。
分三种情况讨论：
1.该区间无优势线段或要插入的线段在该区间内完全在优势线段之上，将该区间的优势线段记为该线段并返回。
2.要插入的线段完全被之前的优势线段覆盖。直接返回
3.否则下放到左右两个子区间。

查询

从根节点走到查询位置的叶子结点。对路径上所有结点的优势节点在查询位置的\(y\)取最大值即可。

时间复杂度

查询一次的时间复杂度显然为\(log(n)\)

修改时，每个线段最多被分为\(log(n)\)段。每段最多被下放\(log(n)\)次。所以修改一次的最坏复杂度为\(log^2(n)\)

代码

luogu4097

/*
* @author: wxyww
* @date:   2019-07-17 08:32:42
* @last modified time: 2019-07-17 10:00:19
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 100000 + 100,mod = 39989,mod2 = 1e9;
const double aps = 1e-8;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

struct node {
    double k,b;
    node() {}
    node(int x1,int x2,int y1,int y2) {
        if(x1 == x2) {
            k = 0;b = max(y1,y2);
            return;
        }
        k = 1.0 * (y2 - y1) / (x2 - x1);
        b = y2 - k * x2;
    }
    double calc(int x) {
        return k * x + b;
    }
}a[n];
int tree[n << 2];
void update(int rt,int l,int r,int l,int r,int x) {
    if(l <= l && r >= r) {
        if(!tree[rt]) {
            tree[rt] = x;
            return;
        }
        if(a[x].calc(r) - a[tree[rt]].calc(r) >= aps && a[x].calc(l) - a[tree[rt]].calc(l) >= aps) {
            tree[rt] = x;
            return;
        }
        if(a[tree[rt]].calc(l) - a[x].calc(l) >= aps && a[tree[rt]].calc(r) - a[x].calc(r) >= aps) return;
        if(l == r) return;
    }
    int mid = (l + r) >> 1;
    if(l <= mid) update(rt << 1,l,mid,l,r,x);
    if(r > mid) update(rt << 1 | 1,mid + 1,r,l,r,x);
}
int ans;
void query(int rt,int l,int r,int pos) {
    if(a[tree[rt]].calc(pos) - a[ans].calc(pos) >= aps) ans = tree[rt];
    if(fabs(a[tree[rt]].calc(pos) - a[ans].calc(pos)) <= aps && ans > tree[rt]) ans = tree[rt];
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) query(rt << 1,l,mid,pos);
    else query(rt << 1 | 1,mid + 1,r,pos);
}
int tot = 0;
int main() {
    int n = read();
    a[0] = node(1,1,-1,-1);
    while(n--) {
        int opt = read();
        if(!opt) {
            int k = (read() + ans - 1) % mod + 1;
            ans = 0;query(1,1,n - 10,k);
            printf("%d\n",ans);
        }
        else {
            int x1 = (read() + ans - 1) % mod + 1,y1 = (read() + ans - 1) % mod2 + 1,x2 = (read() + ans - 1) % mod + 1,y2 = (read() + ans - 1) % mod2 + 1;
            if(x1 > x2) swap(x1,x2),swap(y1,y2);
            a[++tot] = node(x1,x2,y1,y2);
            update(1,1,n - 10,x1,x2,tot);
        }
    }
    return 0;
}