李超线段树80pts求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const int N=40000;
const double eps=1e-9;
struct line{
	double k,b;
};
double kth(double x0,double y0,double x1,double y1){
	if(fabs(x0-x1)<=eps)return 0;
	return (y0-y1)/(x0-x1);
}
double bth(double x0,double y0,double x1,double y1){
	if(fabs(x0-x1)<=eps)return max(y0,y1);
	return y0-x0*kth(x0,y0,x1,y1);
}
double get(double x,double k,double b){
	return k*x+b;
}
struct segtree{
	int sum[N<<2];
	line lazy[N<<2];
	bool used[N<<2];
	int check(int p,int l,int r,double k1,double b1,double k2,double b2){
		if(!used[p])return 1;
		if(l==r){
			if(get(l,k1,b1)-get(l,k2,b2)>eps)return 1;
			else return -1;
		}
		int l1=get(l,k1,b1);
		int r1=get(r,k1,b1);
		int l2=get(l,k2,b2);
		int r2=get(r,k2,b2);
		if(fabs(l1-l2)<=eps&&fabs(r1-r2)<=eps)return -1;
		if(l1-l2>eps&&r1-r2>eps)return 1;
		else if((l1-l2<-eps&&r1-r2>eps)||(l1-l2>eps&&r1-r2<-eps))return 0;
		else if((fabs(l1-l2)<=eps&&r1-r2>eps)||(l1-l2>eps&&fabs(r1-r2)<=eps))return 0;
		else return -1;
	}
	void upd(int p,int l,int r,double k,double b,int id){
		if(check(p,l,r,k,b,lazy[p].k,lazy[p].b)==1){
			lazy[p].k=k;
			lazy[p].b=b;
			sum[p]=id;
			used[p]=1;
			return ;
		}
		if(l==r)return ;
		int mid=(l+r)>>1;
		if(check(p*2,l,mid,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2,l,mid,k,b,id);
		if(check(p*2+1,mid+1,r,k,b,lazy[p].k,lazy[p].b)>=0)upd(p*2+1,mid+1,r,k,b,id);
	}
	void push_down(int p,int l,int r){
		if(!used[p])return ;
		int mid=(l+r)>>1;
		upd(p*2,l,mid,lazy[p].k,lazy[p].b,sum[p]);
		upd(p*2+1,mid+1,r,lazy[p].k,lazy[p].b,sum[p]);
		lazy[p].k=lazy[p].b=sum[p]=0;
		used[p]=0;
	}
	void add(int p,int l,int r,int x,int y,double k,double b,int id){
		if(l>=x&&r<=y){
			upd(p,l,r,k,b,id);
			return ;
		}
		int mid=(l+r)>>1;
		push_down(p,l,r);
		if(mid>=x)add(p*2,l,mid,x,y,k,b,id);
		if(mid<y)add(p*2+1,mid+1,r,x,y,k,b,id);
	}
	int query(int p,int l,int r,int x){
		if(l==r)return sum[p];
		int mid=(l+r)>>1;
		push_down(p,l,r);
		if(mid>=x)return query(p*2,l,mid,x);
		else return query(p*2+1,mid+1,r,x);
	}
}st;
signed main(){
	int q,lastans=0,n=mod1,cnt=0;
	cin>>q;
	while(q--){
		int op,k,x0,y0,x1,y1;
		cin>>op;
		if(op==0){
			cin>>k;
			k=(k+lastans-1)%mod1+1;
			lastans=st.query(1,1,n,k);
			cout<<lastans<<"\n";
		}
		else {
			cnt++;
			cin>>x0>>y0>>x1>>y1;
			x0=(x0+lastans-1)%mod1+1;
			x1=(x1+lastans-1)%mod1+1;
			y0=(y0+lastans-1)%mod2+1;
			y1=(y1+lastans-1)%mod2+1;
			if(x0>x1){
				swap(x0,x1);
				swap(y0,y1);
			}
			long double k=kth(x0,y0,x1,y1);
			long double b=bth(x0,y0,x1,y1);
			st.add(1,1,n,x0,x1,k,b,cnt);
		}
	}
}