kkogoro

BZOJ 3165
李超树模板题与插入直线不同的地方在于只有在当前区间被包含在插入线段的横坐标范围内时才可以进行取优,实际实现时可以分...
扫描右侧二维码阅读全文
14
2019/01

BZOJ 3165

李超树模板题

与插入直线不同的地方在于只有在当前区间被包含在插入线段的横坐标范围内时才可以进行取优,实际实现时可以分成内外两层函数,外层模仿线段树区间修改来找到合适的区间,内层进行取优决策

如果插入线段完全覆盖另一条线段,直接把当前区间的最优线段改成插入线段即可,被覆盖的线段没有必要下放

#include <iostream>
#include <cstdio>


inline int read() {    
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}


const int MAXN = 100007;
const int MAXX = 40007;


struct Line {
    int lx, rx;
    double k, b;
    Line() {}
    Line(int x0, int y0, int x1, int y1) {
        if (x0 == x1) {
            k = 0, b = std::max(y0, y1);
        }
        else {
            if (x0 > x1) std::swap(x0, x1), std::swap(y0, y1);
            k = 1.0 * (y1 - y0) / (x1 - x0);
            b = 1.0 * y0 - k * x0;
        }
        lx = x0, rx = x1;
        return;
    }
    inline double func(int x) {
        return k * x + b;
    }
} line[MAXN];
int tot_line;



namespace LiChaoSegmentTree {
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
    int node[MAXX << 2], cntNode;
    inline bool check(int line1, int line2, int x) {
        if (!line1) return 0; //*************************
        double y1 = line[line1].func(x), y2 = line[line2].func(x);
        return y1 == y2 ? line1 < line2 : y1 > y2; 
    }
    void insert(int cur, int l, int r, int nowline) {
        int mid = (l + r) >> 1;    
        if (line[nowline].lx <= l && r <= line[nowline].rx) {
            bool tagL = line[nowline].func(l) > line[ node[cur] ].func(l);
            bool tagR = line[nowline].func(r) > line[ node[cur] ].func(r);
            if (tagL && tagR) {
                node[cur] = nowline;
            }
            else {
                bool tagM = line[nowline].func(mid) > line[ node[cur] ].func(mid);
                if (tagL) {
                    if (tagM) insert(R(cur), mid + 1, r, node[cur]), node[cur] = nowline;
                    else insert(L(cur), l, mid, nowline);
                }
                if (tagR) {            
                    if (tagM) insert(L(cur), l, mid, node[cur]), node[cur] = nowline;
                    else insert(R(cur), mid + 1, r, nowline);
                }
            }
            return;
        }
        if (line[nowline].lx <= mid) insert(L(cur), l, mid, nowline);
        if (line[nowline].rx > mid) insert(R(cur), mid + 1, r, nowline);
        return;
    }
    void query(int &ans, int cur, int l, int r, int x) {
        if (check(node[cur], ans, x)) ans = node[cur];
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) query(ans, L(cur), l, mid, x);
        else query(ans, R(cur), mid + 1, r, x);
        return;
    }
#undef L
#undef R
}


int main() {
    int n = read(), lastans = 0;
    while (n--) {
        int opt = read();
        if (opt) {
            int x0 = ((read() + lastans - 1) % 39989 + 1);
            int y0 = ((read() + lastans - 1) % 1000000000 + 1);
            int x1 = ((read() + lastans - 1) % 39989 + 1);
            int y1 = ((read() + lastans - 1) % 1000000000 + 1);
            line[++tot_line] = Line(x0, y0, x1, y1);
            LiChaoSegmentTree::insert(1, 1, 39989, tot_line);
        }
        else {
            int x = ((read() + lastans - 1) % 39989 + 1);
            LiChaoSegmentTree::query(lastans = 0, 1, 1, 39989, x);
            printf("%d\n", lastans);
        }
    }
    return 0;
}
Last modification:January 14th, 2019 at 03:08 pm

Leave a Comment