看过这个帖子了

https://www.luogu.com.cn/discuss/831250

但是问题好像不在这里，快调成和oiwiki上代码一样了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100010;
const int mod1 = 39989, mod2 = 1e9;
const double eps = 1e-9;
const int MAXT = 40000;
typedef pair<double,int> PII;
int cmp(double x, double y) {
	if(x-y > eps) {
		return 1;
	}
	if(y-x > eps) {
		return -1;
	}
	return 0;
}
int tree[maxn];
int dian[maxn];
int s[maxn];
struct node{
	double k, b;
}xian[maxn];
int cnt;
int lastans;
double calc(int id, int d) {
	return xian[id].k * d + xian[id].b;
}
void add(int x0, int y0, int x1, int y1) {
	if(x0 == x1) {
		xian[++cnt].k = 0;
		xian[cnt].b = max(y0, y1);
	} else {
		xian[++cnt].k = 1.0 * (y1 - y0) / (x1 - x0);
		xian[cnt].b = y0 - xian[cnt].k * x0;
	}
}
void upd(int root, int cl, int cr, int u) {
	int &v = s[root], mid = cl + cr >> 1;
	int bmid = cmp(calc(u, mid), calc(v, mid));
	if (bmid == 1 || (!bmid and u < v)) swap(u, v);
	int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
	if (bl == 1 or (!bl and u < v)) upd(root*2, cl, mid, u);
	if (br == 1 or (!bl and u < v)) upd(root*2+1, mid+1, cr, u); 
}
void update(int root, int cl, int cr, int l, int r, int u) {
	
	if(l <= cl and cr <= r) {
		upd(root, cl, cr, u);
		return;
	}
	int mid = cl + cr >> 1;
	if(l <= mid) {
		update(root * 2, cl, mid, l, r, u);
	}
	if(r > mid) {
		update(root * 2 + 1, mid+1, cr, l, r, u);
	}
}
PII pmax(PII x, PII y) {  // pair max函数
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}
PII query(int idx, int l, int r, int wh) {
	if(r < wh or l > wh) return {0, 0};
	int mid = l + r >> 1;
	double res = calc(s[idx], wh);
	if(l == r) {
		return {res, s[idx]};
	} 
	return pmax({res, s[idx]}, pmax(query(idx*2, l, mid, wh), query(idx*2+1, mid+1, r, wh)));
} 
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) {
		int opt; cin >> opt;
		if(opt == 1) {
			int x0, y0, x1, y1;
			cin >> x0 >> y0 >> x1 >> y1;
			x0 = (x0 + lastans - 1 + mod1) % mod1 + 1;
			x1 = (x1 + lastans - 1 + mod1) % mod1 + 1;
			y0 = (y0 + lastans - 1 + mod2) % mod2 + 1;
			y1 = (y1 + lastans - 1 + mod2) % mod2 + 1;
			if(x0 > x1) {
				swap(x0, x1); swap(y0, y1);
			}
			add(x0, y0, x1, y1);
			update(1, 1, mod1, x0, x1, cnt);
		} else {
			int k; cin >> k;
			k = (k + lastans - 1 + mod1) % mod1 + 1;
			cout << (lastans = query(1, 1, mod1, k).second) << endl;
		}
	}
	return 0;
}