Sub1全RE

#include<bits/stdc++.h>
using namespace std;
#define D double
#define pl (p<<1)
#define pr (p<<1|1) 
const int N=1e5+10,X=4e4;const D e=1e-12;
struct Line{D k,b;}l[N];
struct node{D a;int b;};
int n,op,k,a,b,c,d,last,cnt,tr[X<<2];
D f(int i,int x){return l[i].k*x+l[i].b;}
int cmp(D a,D b){return a-b>e?1:(b-a>e?-1:0);}
node max(node a,node b){return cmp(a.a,b.a)==-1?b:(cmp(a.a,b.a)==1?a:a.b<b.b?a:b);}
void add(int a,int b,int c,int d){cnt++,a==c?(l[cnt].k=0,l[cnt].b=max(b,d)):(l[cnt].k=(D)(d-b)/(c-a),l[cnt].b=b-a*l[cnt].k);}
void upd(int l,int r,int u,int p){
	int &v=tr[p],mid=l+r>>1,flag=cmp(f(u,mid),f(v,mid));
	if(flag||!flag&&u<v)swap(u,v);
	int fx=cmp(f(u,l),f(v,l)),fy=cmp(f(u,r),f(v,r));
	if(fx||!fx&&u<v)upd(l,mid,u,pl);
	if(fy||!fy&&u<v)upd(mid+1,r,u,pr);
}void update(int l,int r,int le,int ri,int v,int p){
	if(l>=le&&r<=ri)return upd(l,r,v,p);
	int mid=l+r>>1;
	if(le<=mid)update(l,mid,le,ri,v,pl);
	if(ri>mid)update(mid+1,r,le,ri,v,pr);
}node query(int d,int l,int r,int p){
	if(l>d||r<d)return (node){0,0};
	int mid=l+r>>1;
	D res=f(tr[p],d);
	if(l==r)return (node){res,tr[p]};
	return max((node){res,tr[p]},max(query(d,l,mid,pl),query(d,mid+1,r,pr)));
}int main(){
	cin>>n;
	while(n--){
		cin>>op;
		if(!op)cin>>k,k=(k+last-1)%39989+1,cout<<(last=query(k,1,39989,1).b)<<'\n';
		else{
			cin>>a>>b>>c>>d,a=(a+last-1)%39989+1,c=(c+last-1)%39989+1,b=(b+last-1)%1000000000+1,d=(d+last-1)%1000000000+1;
			if(a>c)swap(a,c),swap(b,d);
			add(a,b,c,d),update(1,39989,a,c,cnt,1);
		}
	}return 0;
}