Chlience

【算法】李超线段树
一般来说,李超线段树是用来维护二维平面内某条直线 $x=x_0$ 对于支持添加的某个直线集合相交的所有点中最大/小...
扫描右侧二维码阅读全文
29
2018/12

【算法】李超线段树

一般来说,李超线段树是用来维护二维平面内某条直线 $x=x_0$ 对于支持添加的某个直线集合相交的所有点中最大/小的纵坐标

如果不使用李超线段树,也可以用 $set$ + 二分之类的方法做,但是在这里就不多说了

那么李超线段树是如何实现的呢?

首先,李超线段树维护的是某个区间的 最优线段,也就是和其他线段相比(一对一),比较大的部分更多的一条线段

那么考虑在某个区间内加入一条直线的情况,判断哪个线段是更优的很简单
只需要看线段与 $x=mid$ 的交点,高者更优
如下图所示:

lc1.jpg

在这里,显然 $l_a$ 在当前区间内是优于 $l_b$ 的,也就是 $l-mid$ 整个区间比 $l_b$ 优,并且在 $mid-r$ 部分比 $l_b$ 优

那么显然 $l_b$ 在 $l-mid$ 部分完全不可能有任何贡献,所以直接将 $l_b$ 放到该区间的右儿子处递归处理
同理,如果 $l_a$ 在区间内完全优于 $l_b$,该直线会被直接丢弃

也就是说,找出当前直线可能做出贡献的区间,将其下放

那么每次查询某个 $x=x_0$ 时,只需要在线段树上不断向下递归,每次遇到一个节点就取当前答案和当前直线的最大值,最终结果就是所有直线交点的最大值了

例题:

BZOJ 1568

这个题可以说就是李超线段树练手题了

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 100010;
int n , m;
char str[10];
struct Query {
    int x , id;
    void in(int _id) {scanf("%d" , &x); id = _id;}
}q[N];
int qcnt;
struct Line {
    double k , b , id;
    void in(int _id) {scanf("%lf %lf" , &b , &k); b -= k; id = _id;}
}a[N];
int acnt;
int X[N];
double check(int id , int x) {return a[id].k * x + a[id].b;}
struct tree {
    int bh[N << 2];
    void insert(int x , int l , int r , int id) {
        if(l > r) return;
        if(bh[x] == 0) {bh[x] = id;}
        else {
            if(check(bh[x] , X[mid]) < check(id , X[mid]))
                swap(bh[x] , id);
            if(l == r) return;
            if(check(bh[x] , X[l]) < check(id , X[l]))
                insert(L , l , mid , id);
            if(check(bh[x] , X[r]) < check(id , X[r]))
                insert(R , mid + 1 , r , id);
        }
    }
    double query(int x , int l , int r , int id) {
        if(l > r) return 0;
        double ans = check(bh[x] , q[id].x);
        if(q[id].x == X[mid]) return ans;
        if(q[id].x < X[mid]) return max(ans , query(L , l , mid , id));
        else return max(ans , query(R , mid + 1 , r , id));
    }
}t;
int main() {
    n = read();
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%s" , str);
        if(str[0] == 'Q') {q[++ qcnt].in(i); X[qcnt] = q[qcnt].x;}
        else a[++ acnt].in(i);
    }
    sort(X + 1 , X + qcnt + 1);
    m = unique(X + 1 , X + qcnt + 1) - X - 1;
    int l1 = 1 , l2 = 1;
    for(int i = 1 ; i <= n ; ++ i) {
        if(l2 > acnt || (l1 <= qcnt && q[l1].id < a[l2].id)) {
            printf("%d\n" , max(0 , (int)(t.query(1 , 1 , m , l1) / 100))); ++ l1;
        }
        else {
            t.insert(1 , 1 , m , l2); ++ l2;
        }
    }
    return 0;
}

BZOJ 3165

和之前那个的区别就是线变成了线段,并且需要考虑不存在斜率的情况

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 100010;
const int M = 40010;
const int mod = 39989;
int n;
struct Line {
    double k , b;
    void in(int x0 , int y0 , int x1 , int y1) {
        k = (double)(y1 - y0) / (double)(x1 - x0);
        b = (double) y0 - k * x0;
    }
}a[N];
int acnt;
int ans;
int ud[M] , id_ud[M];
double check(int id , int x) {return a[id].k * x + a[id].b;}
struct tree {
    int bh[M << 2];
    void insert(int x , int l , int r , int ll , int rr , int id) {
        if(l >= ll && r <= rr) {
            if(bh[x] == 0) bh[x] = id;
            else {
                if(check(bh[x] , mid) < check(id , mid))
                    swap(bh[x] , id);
                if(l == r) return;
                if(check(bh[x] , l) < check(id , l))
                    insert(L , l , mid , ll , rr , id);
                if(check(bh[x] , r) < check(id , r))
                    insert(R , mid + 1 , r  , ll , rr , id);
            }
        }
        else {
            if(mid >= ll)
                insert(L , l , mid , ll , rr , id);
            if(mid < rr)
                insert(R , mid + 1 , r , ll , rr , id);
        }
    }
    int query(int x , int l , int r , int pos) {
        int ans = bh[x];
        if(l == r) return ans;
        if(pos <= mid) {
            int lans = query(L , l , mid , pos);
            return check(ans , pos) >= check(lans , pos) ? ans : lans;
        }
        else {
            int rans = query(R , mid + 1 , r , pos);
            return check(ans , pos) >= check(rans , pos) ? ans : rans;
        }
    }
}t;
int main() {
    n = read();
    for(int i = 1 ; i <= n ; ++ i) {
        if(read()) {
            ++ acnt;
            int x0 = (read() + ans - 1) % mod + 1;
            int y0 = (read() + ans - 1) % 1000000000 + 1;
            int x1 = (read() + ans - 1) % mod + 1;
            int y1 = (read() + ans - 1) % 1000000000 + 1;
            if(x0 == x1) {
                if(id_ud[x0] == 0 || ud[x0] < max(y0 , y1)) {
                    id_ud[x0] = acnt;
                    ud[x0] = max(y0 , y1);
                }
            }
            else {
                if(x0 > x1) {
                    swap(x0 , x1);
                    swap(y0 , y1);
                }
                a[acnt].in(x0 , y0 , x1 , y1);
                t.insert(1 , 1 , 39989 , x0 , x1 , acnt);
            }
        }
        else {
            int k = (read() + ans - 1) % mod + 1;
            ans = t.query(1 , 1 , 39989 , k);
            if(!ans || (id_ud[k] && ud[k] > check(ans , k)))
                ans = id_ud[k];
            printf("%d\n" , ans);
        }
    }
    return 0;
}
Last modification:December 29th, 2018 at 05:24 pm

Leave a Comment