沟槽的公式，真是公公又式式啊。
考虑一个线段树节点维护一个线段（但一条线段可以被多个线段树节点维护），需要保证该节点被线段完全覆盖。
每次添加一个线段的时候：
-
如果当前节点没有被这个线段完全覆盖，那么直接递归左右儿子修改。
-
如果当前节点的线段比新线段严格劣（也就是对于每一个 \(x\) 都有 \(y_{old}<y_{new}\) 或者 \(y_{old}=y_{new}\) 且编号比新线段大），则这条线段在该节点维护的区间上不再可能成为答案，直接用新线段替换掉。
-
同理，如果新线段严格劣，则直接停止递归，新线段在这个节点上不再可能成为答案。
-
如果新老线段有交点，设其交点的 \(x\) 轴为 \(p\)，若 \(p\le mid\)，则说明在右半区间，一定有一个线段比另一个完全优，则直接把当前的节点维护的线段改为这个完全优的线段，将那个劣的线段下放到 \([l,mid]\) 修改。\(p>mid\) 同理。
然后发现这玩意，如果你有交点，那么你必定把递归的区间缩小了一半，所以你最多递归 \(\log n\) 次，然后由于每个线段在线段树上可以被 \(\log n\) 个区间表示，所以每次修改的复杂度是 \(O(\log ^2n)\) 的，注意这里的 \(n\) 指的是线段树的大小。
对于询问位置 \(x\)，答案是在线段树上维护 \([x,x]\) 这个区间的节点与其所有祖先的答案最大值。
所以最终复杂度 \(O(q\log^2 n)\)，其中 \(q\) 是修改次数。
const int MAXN = 1e6 + 5, N = 39989, mxn = 4e5 + 5;
int n;
struct _node {
int x1, y1, x2, y2, id;
// ensure that x1 <= x2
} tr[MAXN << 2];
double getVal(_node x, int pos) {
if (pos < x.x1 || pos > x.x2) return 0;
if (x.x1 == x.x2) return max(x.y1, x.y2);
const auto k = (x.y2 - x.y1) * 1.0 / (x.x2 - x.x1);
return (pos - x.x1) * 1.0 * k + x.y1;
}
void insert(int p, int l, int r, _node v) {
if (v.x1 <= l && r <= v.x2) {
const auto vl1 = getVal(tr[p], l), vr1 = getVal(tr[p], r);
const auto vl2 = getVal(v, l), vr2 = getVal(v, r);
if (vl1 < vl2 && vr1 < vr2) return tr[p] = v, void();
if (vl1 == vl2 && vr1 == vr2 && tr[p].id > v.id) return tr[p] = v, void();
if (vl2 < vl1 && vr2 < vr1) return;
if (vl1 == vl2 && vr1 == vr2 && tr[p].id < v.id) return;
const auto vm1 = getVal(tr[p], mid), vm2 = getVal(v, mid);
if (vl1 <= vl2) {
if (vm1 <= vm2) insert(rson, mid + 1, r, tr[p]), tr[p] = v;
else insert(lson, l, mid, v);
}
else {
if (vm1 <= vm2) insert(lson, l, mid, tr[p]), tr[p] = v;
else insert(rson, mid + 1, r, v);
}
return;
}
if (v.x1 <= mid) insert(lson, l, mid, v);
if (mid < v.x2) insert(rson, mid + 1, r, v);
}
pair<double, int> mx(pair<double, int> a, pair<double, int> b) {
if (a.first == b.first) return a.second < b.second ? a : b;
return a.first > b.first ? a : b;
}
pair<double, int> query(int p, int l, int r, int pos) {
if (l == r) return make_pair(getVal(tr[p], pos), tr[p].id);
if (pos <= mid) return mx(make_pair(getVal(tr[p], pos), tr[p].id), query(lson, l, mid, pos));
else return mx(make_pair(getVal(tr[p], pos), tr[p].id), query(rson, mid + 1, r, pos));
}
int lastAns, id;
void work() {
cin >> n;
while (n--) {
int opt, k, x1, y1, x2, y2;
cin >> opt;
if (opt == 0) {
cin >> k;
k = (k + lastAns - 1 + N) % N + 1;
const auto ans = query(1, 1, mxn, k);
cout << (lastAns = ans.second) << endl;
}
if (opt == 1) {
cin >> x1 >> y1 >> x2 >> y2;
x1 = (x1 + lastAns - 1 + N) % N + 1;
x2 = (x2 + lastAns - 1 + N) % N + 1;
y1 = (y1 + lastAns - 1 + (int)1e9) % (int)(1e9) + 1;
y2 = (y2 + lastAns - 1 + (int)1e9) % (int)(1e9) + 1;
if (x1 > x2) swap(x1, x2), swap(y1, y2);
insert(1, 1, mxn, {x1, y1, x2, y2, ++id});
}
}
}