李超线段树的模板。但是因为我实在太\(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);
}
}
}