P4097【模板】李超线段树 / [HEOI2013] Segment 模板

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
int T, Lastans, n = 39989, m, Tcnt, Rt, ansid;
struct Line { double k, b; } a[1000005];
struct Tree { int ls, rs, id; } tr[10000005];
bool pd(int i, int j, int x) {if (a[i].k * x + a[i].b - a[j].k * x - a[j].b > eps)return true;if (a[j].k * x + a[j].b - a[i].k * x - a[i].b > eps)return false;return i < j;
}
void change(int &x, int l, int r, int sl, int sr, int now) {if (r < sl || sr < l)return ;if (!x)x = ++Tcnt;if (sl <= l && r <= sr) {if (pd(now, tr[x].id, l) && pd(now, tr[x].id, r)) {tr[x].id = now;return ;}if (pd(tr[x].id, now, l) && pd(tr[x].id, now, r))return ;int mid = (l + r) >> 1;if (pd(now, tr[x].id, mid))swap(now, tr[x].id);if (pd(now, tr[x].id, l))change(tr[x].ls, l, mid, sl, sr, now);if (pd(now, tr[x].id, r))change(tr[x].rs, mid + 1, r, sl, sr, now);}else {int mid = (l + r) >> 1;change(tr[x].ls, l, mid, sl, sr, now), change(tr[x].rs, mid + 1, r, sl, sr, now);}
}
void solve(int x, int l, int r, int s) {if (!x || r < s || s < l)return ;if (pd(tr[x].id, ansid, s))ansid = tr[x].id;if (l == r)return ;int mid = (l + r) >> 1;solve(tr[x].ls, l, mid, s), solve(tr[x].rs, mid + 1, r, s);
}
int main() {// freopen("test.in", "r", stdin);// freopen("test.out", "w", stdout);scanf("%d", &T);while (T--) {int id;scanf("%d", &id);if (id == 0) {int x;ansid = 0;scanf("%d", &x), x = (x + Lastans - 1) % n + 1;solve(1, 1, n, x), Lastans = ansid;printf("%d\n", ansid);}else {int sx, sy, ex, ey;scanf("%d%d%d%d", &sx, &sy, &ex, &ey);sx = (sx + Lastans - 1) % n + 1, sy = (sy + Lastans - 1) % 1000000000 + 1, ex = (ex + Lastans - 1) % n + 1, ey = (ey + Lastans - 1) % 1000000000 + 1;if (ex < sx)swap(sx, ex), swap(sy, ey);if (ex != sx)m++, a[m].k = 1.0 * (ey - sy) / (ex - sx), a[m].b = 1.0 * sy - a[m].k * sx;elsem++, a[m].k = 0, a[m].b = max(sy, ey);// a[m].k *= 10, a[m].b *= 10;change(Rt, 1, n, sx, ex, m);}}return 0;
}