题目在这

WA on #13 #14 #16

#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
#define lf double
const ll MODX = 39989;
const ll MODY = 1e9;
const ll INF = 99999999;
const lf EPS = 1e-7;
struct Line {
	lf k, b;
	ll l, r;
} lines[100005];
int idle = 0;
int tree[620000] = { 0 };
struct Ans {
	lf val;
	int ind;
};
inline ll offset_x(ll x, int las) { return (x + las - 1 + MODX) % MODX + 1; }
inline ll offset_y(ll y, int las) { return (y + las - 1 + MODY) % MODY + 1; }
lf get_y(int line, ll x) {
	if (x < lines[line].l || x > lines[line].r) return -INF;
	return lines[line].k * x + lines[line].b;
}
int compare(lf a, lf b) { // 1 : a == b   2 : a > b   3 : a < b
	if (fabs(a - b) <= EPS) return 1;
	if (a > b) return 2;
	return 3;
}
void insert(int node, ll l, ll r, int line) { // 当前节点以及当前节点管辖范围
	ll L = lines[line].l, R = lines[line].r;
	ll mid = (l + r) / 2;
	if (L <= l && r <= R) {
		if (tree[node] == 0) {
			tree[node] = line;
			return;
		}
		int old_line = tree[node];
		if (compare(lines[old_line].k, lines[line].k) == 1 && //与当前线段重合，但是编号更小
			compare(lines[old_line].b, lines[line].b) == 1 && line < old_line) {
			tree[node] = line;
			return;
		}
		lf old_l = get_y(old_line, l), old_r = get_y(old_line, r);
		lf l_val = get_y(line, l), r_val = get_y(line, r);
		if (compare(l_val, old_l) == 2 && compare(r_val, old_r) == 2) { //完全覆盖当前区间
			tree[node] = line;
			return;
		}
		lf old_mid = get_y(old_line, mid), mid_val = get_y(line, mid);
		int ret = compare(mid_val, old_mid);
		if (compare(l_val, old_l) == 2 || compare(r_val, old_r) == 2) { //两边至少有一个点优于当前线段
			if (ret == 2 || (ret == 1 && line < old_line))
				tree[node] = line,
				swap(line, old_line);
			if (l == r) return; // 没孩子不用递归考虑
			ret = compare(get_y(line, l), get_y(tree[node], l));
			if (ret == 2 || (ret == 1 && line < tree[node]))
				insert(node * 2, l, mid, line);
			ret = compare(get_y(line, r), get_y(tree[node], r));
			if (ret == 2 || (ret == 1 && line < tree[node]))
				insert(node * 2 + 1, mid + 1, r, line);
		}
		return;
	}
	if (L <= mid) insert(node * 2, l, mid, line);
	if (R > mid) insert(node * 2 + 1, mid + 1, r, line);
}
Ans max_ans(Ans a, Ans b) {
	if (fabs(a.val - b.val) <= EPS) {
		if (a.ind < b.ind) return a;
		return b;
	}
	if (a.val > b.val) return a;
	return b;
}
Ans query(int node, ll l, ll r, ll x) {
	Ans ret = { -INF, 0 };
	if (x < l || x > r) return ret;
	ret.val = get_y(tree[node], x);
	ret.ind = tree[node];
	if (l == r) return ret;
	ll mid = (l + r) / 2;
	if (x <= mid) ret = max_ans(ret, query(node * 2, l, mid, x));
	else ret = max_ans(ret, query(node * 2 + 1, mid + 1, r, x));
	return ret;
}
int main() {
	int _, las = 0;
	scanf("%d", &_);
	while (_--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			ll x1, y1, x2, y2;
			scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
			x1 = offset_x(x1, las);
			x2 = offset_x(x2, las);
			y1 = offset_y(y1, las);
			y2 = offset_y(y2, las);
			idle++;
			if (x1 > x2) swap(x1, x2), swap(y1, y2);
			if (x1 == x2) lines[idle].k = 0, lines[idle].b = max(y2, y1);
			else lines[idle].k = ((y2 - y1) * 1.0f) / ((x2 - x1) * 1.0f),
				lines[idle].b = y1 * 1.0f - lines[idle].k * (x1 * 1.0f);
			lines[idle].l = x1, lines[idle].r = x2;
			insert(1, 1, MODX, idle);
		}
		else {
			ll x;
			scanf("%lld", &x);
			x = offset_x(x, las);
			Ans ans = query(1, 1, MODX, x);
			las = ans.ind;
			printf("%d\n", las);
		}
	}
	return 0;
}