数据疑似太水

#include <bits/stdc++.h>

using namespace std;
typedef double db;
const int inf = 0x3f3f3f3f;
const db eps = 1e-9;

int n;

struct Line {
    db k, b;
    Line() {
        k = b = ~inf;
    }
    Line(int x, int y, int xx, int yy) {
        k = 1. * (yy - y) / (xx - x);
        b = y - k * x;
    }
    db getY(int x) {
        return k * x + b;
    }
};
struct Tag {
    Line l;
    int id;
    Tag() {
        l = Line();
        id = 0;
    }
    Tag(int y, int i) {
        l.k = 0;
        l.b = y * 1.;
        id = i;
    }
    Tag(int a, int b, int c, int d, int i) {
        l = Line(a, b, c, d);
        id = i;
    }
    db getY(int x) {
        return l.getY(x);
    }
};
bool operator==(Tag a, Tag b) {
    return (a.l.k == b.l.k) && (a.l.b == b.l.b) && (a.id == b.id);
}
struct SegmentTree {
    int sz;
    vector<Tag> tag;
    Tag ide;

    SegmentTree(){}
    SegmentTree(int n) {
        for (sz = 1; sz < n; sz *= 2);
        tag.assign(2 * sz, ide);
    }
    int cmp(Tag a, Tag b, int lx, int rx) {
        if (a.getY(lx) > b.getY(lx) && a.getY(rx) > b.getY(rx))
            return 1;
        if (a.getY(lx) <= b.getY(lx) && a.getY(rx) <= b.getY(rx))
            return 0;
        return 2;
    }
    void mktag(int x, int lx, int rx, Tag v) {
        if (tag[x] == ide) {
            tag[x] = v;
            return ;
        }
        if (lx + 1 == rx) {
            if ((v.getY(lx) - tag[x].getY(lx) > eps) || (fabs(v.getY(lx) - tag[x].getY(lx)) < eps && v.id < tag[x].id))
                tag[x] = v;
            return ;
        }
        int typ = cmp(tag[x], v, lx, rx);
        if (typ == 1)
            return ;
        if (typ == 0) {
            tag[x] = v;
            return ;
        }

        int m = (lx + rx) / 2;
        mktag(x * 2, lx, m, v);
        mktag(x * 2 + 1, m, rx, v);
    }
    void pushdown(int x, int lx, int rx) {
        if (tag[x] == ide)
            return ;
        int m = (lx + rx) / 2;
        mktag(x * 2, lx, m, tag[x]);
        mktag(x * 2 + 1, m, rx, tag[x]);
        tag[x] = ide;
    }
    void mdf(int x, int lx, int rx, int l, int r, Tag v) {
        if (l <= lx && rx <= r) {
            mktag(x, lx, rx, v);
            return ;
        }
        if (l >= rx || lx >= r)
            return ;
        int m = (lx + rx) / 2;
        mdf(x * 2, lx, m, l, r, v);
        mdf(x * 2 + 1, m, rx, l, r, v);
    }
    Tag qry(int x, int lx, int rx, int p) {
        if (lx + 1 == rx)
            return tag[x];
        int m = (lx + rx) / 2;
        Tag tmp;
        if (p < m)
            tmp = qry(x * 2, lx, m, p);
        else
            tmp = qry(x * 2 + 1, m, rx, p);
        if ((tmp.getY(p) - tag[x].getY(p) > eps) || (fabs(tmp.getY(p) - tag[x].getY(p)) < eps && tmp.id < tag[x].id))
            return tmp;
        return tag[x];
    }
} st;

int main() {
    st = SegmentTree(40000);
    cin >> n;
    int lst = 0;
    for (int i = 1, op, a, b, c, d, cnt = 0; i <= n; i++) {
        cin >> op;
        if (op == 0) {
            cin >> a;
            a = (a + lst - 1) % 39989 + 1;
            int t = st.qry(1, 1, st.sz + 1, a).id;
            cout << t << endl;
            lst = t;
        }
        else {
            cin >> a >> b >> c >> d;
            a = (a + lst - 1) % 39989 + 1;
            b = (b + lst - 1) % 1000000000 + 1;
            c = (c + lst - 1) % 39989 + 1;
            d = (d + lst - 1) % 1000000000 + 1;
            if (a > c)
                swap(a, c), swap(b, d);
            //特判垂直于x轴
            cnt++;
            if (a != c) {
                st.mdf(1, 1, st.sz + 1, a, c + 1, Tag(a, b, c, d, cnt));
            }
            else {
                st.mdf(1, 1, st.sz + 1, a, a + 1, Tag(max(b, d), i));
            }
        }
    }
    return 0;
}

这是我的AC代码。

可以看到我的 mktag（给某个结点打标记）的函数里面是同时向两个儿子递归了，但还是通过了。

还是说这里有什么神奇的地方使我的代码飞快。