这就是我们的李超线段树啊，你们有没有这样的李超线段树啊？

作者：XiaoQuQu，发表于 Sat Feb 24 2024。

沟槽的公式，真是公公又式式啊。

考虑一个线段树节点维护一个线段（但一条线段可以被多个线段树节点维护），需要保证该节点被线段完全覆盖。

每次添加一个线段的时候：

1. 如果当前节点没有被这个线段完全覆盖，那么直接递归左右儿子修改。

2. 如果当前节点的线段比新线段严格劣（也就是对于每一个 $x$ 都有 $y_{old}<y_{new}$ 或者 $y_{old}=y_{new}$ 且编号比新线段大），则这条线段在该节点维护的区间上不再可能成为答案，直接用新线段替换掉。

3. 同理，如果新线段严格劣，则直接停止递归，新线段在这个节点上不再可能成为答案。

4. 如果新老线段有交点，设其交点的 $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});
		}
	}
}