李超线段树

功能

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

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;
}

原文链接:https://www.cnblogs.com/wxyww/p/lichaotree.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有