欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ3165: [Heoi2013]Segment(李超线段树)

程序员文章站 2022-05-26 22:55:46
题意 "题目链接" Sol 李超线段树板子题。具体原理就不讲了。 一开始自己yy着写差点写自闭都快把叉积搬出来了。。。 后来看了下litble的写法才发现原来可以写的这么清晰简洁Orz ......

题意

题目链接

sol

李超线段树板子题。具体原理就不讲了。

一开始自己yy着写差点写自闭都快把叉积搬出来了。。。

后来看了下litble的写法才发现原来可以写的这么清晰简洁orz

#include<bits/stdc++.h>
#define pdd pair<double, double> 
#define mp make_pair
#define fi first
#define se second 
using namespace std;
const int maxn = 1e6 + 10, lim = 1e9;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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;
}
int n = 39989, m;
int ls[maxn], rs[maxn], root, cnt, tot;
pdd mx[maxn];
struct line {
    double k, b;
    int id;
}s[maxn];
pdd get(int x0, int y0, int x1, int y1) {
    double k = (double) (y1 - y0) / (x1 - x0),
           b = (double) y0 - k * x0;
    return {k, b};
}
double calc(line line, int x) {
    return line.k * x + line.b;
}
double getpoint(line a, line b) {
    return (b.b - a.b) / (a.k - b.k);
}
pdd ret;
void query(int k, int l, int r, int p) {//fi: val  se: id
    if(chmax(ret.fi, calc(s[k], p))) ret.se = s[k].id;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(p <= mid) query(ls[k], l, mid, p);
    else query(rs[k], mid + 1, r, p);
}
void modify(int &k, int l, int r, int ql, int qr, line seg) {
    if(!k) k = ++tot;
    int mid = l + r >> 1;
    if(ql <= l && r <= qr) {
        if(!s[k].id) {s[k] = seg; return ;}
        int p = getpoint(s[k], seg);
        int pl = calc(s[k], l), pr = calc(s[k], r), nl = calc(seg, l), nr = calc(seg, r);
        if(pl > nl && pr > nr) return ;
        if(pl < nl && pr < nr) {s[k] = seg; return ;}
        if(pl < nl) {
            if(p > mid) modify(rs[k], mid + 1, r, mid + 1, r, s[k]), s[k] = seg;
            else modify(ls[k], l, mid, l, mid, seg);
        } else {
            if(p > mid) modify(rs[k], mid + 1, r, mid + 1, r, seg);
            else modify(ls[k], l, mid, l, mid, s[k]), s[k] = seg;
        }
        return ;
    }
    if(l == r) return ;
    if(ql <= mid) modify(ls[k], l, mid, ql, qr, seg);
    if(qr  > mid) modify(rs[k], mid + 1, r, ql, qr, seg);
}
signed main() {
    m = read();
    for(int i = 1, lastans = 0; i <= m; i++) {
        int opt = read();
        if(!opt) {
            int k = read(), x = (k + lastans - 1) % 39989 + 1;
            ret.fi = 0; ret.se = 0;
            query(root, 1, n, x);
            printf("%d\n", lastans = (mx[x].fi > ret.fi ? mx[x].se : ret.se));
        } else {
            int x0 = (read() + lastans - 1) % 39989 + 1, y0 = (read() + lastans - 1) % lim + 1,
                x1 = (read() + lastans - 1) % 39989 + 1, y1 = (read() + lastans - 1) % lim + 1;
            if(x0 > x1) swap(x0, x1), swap(y0, y1);
            if(x0 == x1 && chmax(mx[x0].fi, max(y0, y1))) mx[x0].se = i;
            pdd li = get(x0, y0, x1, y1);
            modify(root, 1, n, x0, x1, {li.fi, li.se, ++cnt});
        }
    }
    return 0;
}