题目描述

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ 。
2. 给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。

强制在线。

题解

李超树板题。在点上维护线段。

代码

const int N = 100005;
const int mod = 39989;
const double eps = 1e-4;


inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {

	int n;

	struct Line {
		double k, b;
		int id;
		Line (double k = 0, double b = 0, int id = 0):k(k), b(b), id(id){}

		inline double val(int pos) { return k * pos + b; }
		inline double cross (const Line &T) { return (T.b - b) / (k - T.k); }
	};

	
	struct Pair {
		double val;
		int id;
		Pair (double val, int id): val(val), id(id) {}
		Pair (){}
	};


	struct SegmentTree {
		struct node {
			int l, r; 
			Line L;
			bool flag; // is it has best one
			node (int l, int r, Line L, bool flag):l(l), r(r), L(L), flag(flag){}
			node (){}
		}t[N << 2];

		void Build (int p, int l, int r) {
			t[p] = node(l, r, Line(), 0);
			if (l == r) return ;
			int mid = l + r >> 1;
			Build (p << 1, l, mid);
			Build (p << 1 | 1, mid + 1, r);
		}

		void Modify (int p, int l, int r, Line L) {
			if (l <= t[p].l && t[p].r <= r) {
				double lp = t[p].L.val(t[p].l), rp = t[p].L.val(t[p].r);
				double lq = L.val(t[p].l), rq = L.val(t[p].r);

				if (!t[p].flag) t[p].L = L, t[p].flag = 1;
				else if (lq - lp > eps && rq - rp > eps) t[p].L = L;
				else if (lq - lp > eps || rq - rp > eps) {
					int mid = t[p].l + t[p].r >> 1;
					if (L.val(mid) - t[p].L.val(mid) > eps) swap (t[p].L, L);
					if (L.val(t[p].l) > t[p].L.val(t[p].l)) Modify (p << 1, l, r, L);
					else Modify (p << 1 | 1, l, r, L);
				}
			} else {
				int mid = t[p].l + t[p].r >> 1;
				if (l <= mid) Modify(p << 1, l, r, L);
				if (r > mid) Modify (p << 1 | 1, l, r, L);
			}
		}

		Pair Query (int p, int pos) {
			double ans = t[p].L.val(pos);
			int id = t[p].L.id;
			if (t[p].l == t[p].r) return Pair(ans, id);
			int mid = t[p].l + t[p].r >> 1;
			if (pos <= mid) {
				Pair lq = Query (p << 1, pos);
				if (lq.val > ans || (fabs(lq.val - ans) < eps && lq.id < id))
					ans = lq.val, id = lq.id;
			} else {
				Pair rq = Query (p << 1 | 1, pos);
				if (rq.val > ans || (fabs(rq.val - ans) < eps && rq.id < id))
					ans = rq.val, id = rq.id;
			}
			return Pair(ans, id);
		}
	}t;

	int main() {
		n = Read();
		t.Build(1, 1, 40000);
		for (int i = 1, lst = 0, cnt = 0; i <= n; i++) {
			int opt = Read();
			if (opt) {
				int x0 = (Read() + lst - 1) % mod + 1, y0 = (Read() + lst - 1) % 1000000000 + 1, x1 = (Read() + lst - 1) % mod + 1, y1 = (Read() + lst - 1) % 1000000000 + 1;
				if (x1 < x0) x1 ^= x0 ^= x1 ^= x0, y1 ^= y0 ^= y1 ^= y0;
				Line L;
				cnt ++;
				if (x0 == x1) {
					L = Line(0.0, max(y0, y1), cnt);
				} else {
					double k = 1.0 * (y1 - y0) / (x1 - x0);
					L = Line(k, 1.0 * y0 - k * x0, cnt);
				}
				t.Modify(1, x0, x1, L);
			} else {
				int x = Read();
				x = (x + lst - 1) % mod + 1;
				printf ("%d\n", (lst = t.Query(1, x).id));
			}
		}
		return 0;
	}
}

int main() {
//	freopen("P4097_8.in", "r", stdin);
//	freopen(".out", "w", stdout);
	return Main::main();
}