Luogu-P4097 Segment

要求在平面直角坐标系下维护两个操作：

  1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。
  2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。
1
#include <iostream>
2
#include <cstdio>
3
#define ls (o << 1)
4
#define rs (o << 1 | 1)
5
using namespace std;
6
const int N = 1E5 + 7;
7
const int M = 39989;
8
const int M2 = 1E9;
9
struct Line{
10
    double k, b;
11
}ll[N];
12
int cnt;
13
void add(int x0, int y0, int x1, int y1){
14
    cnt++;
15
    if(x0 == x1){
16
        ll[cnt].k = 0; ll[cnt].b = max(y0, y1);
17
    }
18
    else{
19
        ll[cnt].k = 1.0 * (y1 - y0) / (x1 - x0);
20
        ll[cnt].b = y0 - ll[cnt].k * x0;
21
    }
22
}
23
int t[M << 2];
24
double cal(int x, int id){
25
    return ll[id].k * x + ll[id].b;
26
}
27
void update(int o, int l, int r, int xl, int xr, int id){
28
    if(xl > r || xr < l) return;
29
    int mid = (l + r) >> 1;
30
    int nw = t[o];
31
    double ynw = cal(mid, nw), yid = cal(mid, id);
32
    if(xl <= l && r <= xr){
33
        if(l == r){
34
            if(ynw < yid) t[o] = id;
35
            return;
36
        }
37
        if(ll[nw].k == ll[id].k){
38
            if(ll[nw].b < ll[id].b) t[o] = id;
39
        }
40
        else if(ll[nw].k < ll[id].k){
41
            if(ynw >= yid){
42
                update(rs, mid + 1, r, xl, xr, id);
43
            }
44
            else{
45
                t[o] = id;
46
                update(ls, l, mid, xl, xr, nw);
47
            }
48
        }
49
        else if(ll[nw].k > ll[id].k){
50
            if(ynw >= yid){
51
                update(ls, l, mid, xl, xr, id);
52
            }
53
            else{
54
                t[o] = id;
55
                update(rs, mid + 1, r, xl, xr, nw);
56
            }
57
        }
58
        return;
59
    }
60
    if(xl <= mid) update(ls, l, mid, xl, xr, id);
61
    if(xr > mid) update(rs, mid + 1, r, xl, xr, id);
62
}
63
typedef pair<double, int> pdi;
64
bool cmp(const pdi &a, const pdi &b){
65
    if(a.first == b.first) return a.second < b.second;
66
    return a.first > b.first;
67
}
68
pdi query(int o, int l, int r, int x){
69
    if(x > r || x < l) return {0, 0};
70
    pdi res = {cal(x, t[o]), t[o]};
71
    if(l == r) return res;
72
    int mid = (l + r) >> 1;
73
    pdi tmp;
74
    if(x <= mid) tmp = query(ls, l, mid, x);
75
    else tmp = query(rs, mid + 1, r, x);
76
    if(cmp(tmp, res)) res = tmp;
77
    return res;
78
}
79
int main(){
80
    int n, op, k, x, x0, y0, x1, y1, xx0, yy0, xx1, yy1;
81
    scanf("%d", &n);
82
    int ans = 0;
83
    for(int i = 1; i <= n; i++){
84
        scanf("%d", &op);
85
        if(op == 0){
86
            scanf("%d", &k);
87
            x = (k + ans - 1) % M + 1;
88
            ans = query(1, 1, M, x).second;
89
            printf("%d\n", ans);
90
        }
91
        else{
92
            scanf("%d%d%d%d", &xx0, &yy0, &xx1, &yy1);
93
            x0 = (xx0 + ans - 1) % M + 1;
94
            x1 = (xx1 + ans - 1) % M + 1;
95
            y0 = (yy0 + ans - 1) % M2 + 1;
96
            y1 = (yy1 + ans - 1) % M2 + 1;
97
            if(x0 > x1){
98
                swap(x0, x1);
99
                swap(y0, y1);
100
            }
101
            add(x0, y0, x1, y1);
102
            update(1, 1, M, x0, x1, cnt);
103
        }
104
    }
105
    return 0;
106
}