Luogu P4097 [HEOI2013]Segment 李超线段树

墨蓝 2022-01-09 10:49 199阅读 0赞

#### [题目链接 \\(Click\\) \\(Here\\)][_Click_ _Here] ####

#### 李超线段树的模板。但是因为我实在太\\(Naive\\)了，想象不到实现方法。 ####

#### 看代码就能懂的东西，放在这里用于复习。 ####

#include <bits/stdc++.h> using namespace std; const int N = 100010; #define ls (p << 1) #define rs (p << 1 | 1) #define mid ((l + r) >> 1) struct Node { int l, r, id; double yl, yr; Node (int x1 = 0, int y1 = 0, int x2 = 0, int y2 = 0, int i = 0) { l = x1, r = x2, yl = y1, yr = y2, id = i; if (l == r) { yl = yr = max (yl, yr); } } double get (int x) {return l == r ? yl : yl + (k () * (x - l));} double k () {return (yr - yl) / (r - l);} void lm (int x) {yl = get (x); l = x;} void rm (int x) {yr = get (x); r = x;} }; bool hei (Node a, Node b, int x) { return a.get (x) == b.get (x) ? a.id < b.id : a.get (x) > b.get (x); } struct St { Node tree[N << 2]; void build (int l, int r, int p) { tree[p].l = l; tree[p].r = r; if (l == r) return; build (l, mid, ls); build (mid + 1, r, rs); } Node query (int t, int l, int r, int p) { if (l == r) return tree[p]; Node res; if (t <= mid) { res = query (t, l, mid, ls); } else { res = query (t, mid + 1, r, rs); } return hei (res, tree[p], t) ? res : tree[p]; } void update (int l, int r, Node k, int p) { if (tree[p].l > k.l) k.lm (tree[p].l); if (tree[p].r < k.r) k.rm (tree[p].r); //削足适履 if (hei (k, tree[p], mid)) swap (tree[p], k); //让tree[p]在mid上具有优势 if (min (tree[p].yl, tree[p].yr) >= max (k.yl, k.yr)) return; //如果完全覆盖 if (l == r) return; //如果大小为1 if (tree[p].k () <= k.k ()) { update (mid + 1, r, k, rs); //如果k在后面有露出来的情况 } else { update (l, mid, k, ls); //如果k在前面有露出来的情况 } } void insert (int l, int r, Node k, int p) { if (k.l > r || k.r < l) return; if (tree[p].l > k.l) k.lm (tree[p].l); if (tree[p].r < k.r) k.rm (tree[p].r); if (l == k.l && r == k.r) { update (l, r, k, p); return; } //把node一路传下去，对应区间就削成对应大小的线段 if (l == r) return; insert (l, mid, k, ls); insert (mid + 1, r, k, rs); } }T; const int My = 1e9; const int Mx = 39989; int m, k, la, Ind, opt; int main () { T.build (1, Mx, 1); cin >> m; while (m--) { cin >> opt; if (opt == 0) { cin >> k; k = (k + la - 1) % Mx + 1; la = T.query (k, 1, Mx, 1).id; cout << la << endl; } else { int x0, x1, y0, y1; cin >> x0 >> y0 >> x1 >> y1; x0 = (x0 + la - 1) % Mx + 1; x1 = (x1 + la - 1) % Mx + 1; y0 = (y0 + la - 1) % My + 1; y1 = (y1 + la - 1) % My + 1; if (x0 > x1) { swap (x0, x1); swap (y0, y1); } Node res = Node (x0, y0, x1, y1, ++Ind); T.insert (1, Mx, res, 1); } } }

转载于:https://www.cnblogs.com/maomao9173/p/10444517.html

[_Click_ _Here]: https://www.luogu.org/problemnew/show/P4097