MnZn 100pts求助

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForD(i,j,k) for(int i=(j);i>=(k);--i)
#define ll long long
#define MOD1 39989
#define MOD2 1000000000
#define pdi pair<double,int>
using namespace std;
const int eps=1e-9;
int n,lastans=0;
int cnt=0;
int s[200005];
struct line{
	double k,b;
}p[200005];
int cmp(double x,double y){
	if((x-y)>eps) return 1;
	if((y-x)>eps) return -1;
	return 0;
}
double calc(int x,int pos){
	return p[x].b+p[x].k*pos;
}
void add(int x0,int y0,int x1,int y1){
	cnt++;
	if(x0==x1)p[cnt].k=0,p[cnt].b=max(y0,y1);
	else p[cnt].k=1.0*(y1-y0)/(x1-x0),p[cnt].b=y1-p[cnt].k*x1;
	return;
}
void upd(int node,int l,int r,int u){
	int &v=s[node],mid=l+r>>1;
	if(cmp(calc(u,mid),calc(v,mid))==1) swap(u,v);
	int bl=cmp(calc(u,l),calc(v,l)),br=cmp(calc(u,r),calc(v,r));
	if(bl==1||(bl==0&&u<v)) upd(node<<1,l,mid,u);
	if(br==1||(br==0&&u<v)) upd(node<<1|1,mid+1,r,u);
	return;
}
void modify(int node,int l,int r,int ql,int qr,int u){
	if(l>=ql&&r<=qr){
		upd(node,l,r,u);
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) modify(node<<1,l,mid,ql,qr,u);
	if(qr>mid) modify(node<<1|1,mid+1,r,ql,qr,u);
	return;
}
pdi pmax(pdi x,pdi y){
	int res=cmp(x.first,y.first);
	if(res==1)return x;
	else if(res==-1)return y;
	if(x.second<y.second)return x;
	return y;
}
pdi query(int node,int l,int r,int u){
	if(u<l||u>r)return{0,0};
	int mid=l+r>>1;
	double res=calc(s[node],u);
	if(l==r)return {res,s[node]};
	return pmax({res,s[node]},pmax(query(node<<1,l,mid,u),query(node<<1|1,mid+1,r,u)));
}
int main(){
	//freopen("P4097.in","r",stdin);
	//freopen("P4097.out","w",stdout);
	cin>>n;
	For(i,1,n){
		int op;cin>>op;
		if(op==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);
			modify(1,1,MOD1,x0,x1,cnt);
		}else{
			int x;cin>>x;
//			if(n==3&&x==8){
//				cout<<1<<endl;
//				return 0;
//			}
			x = (x+lastans-1+MOD1) % MOD1 + 1;
			lastans=query(1,1,MOD1,x).second;
			cout<<lastans<<endl;
		}
	}
	return 0;
}