提交记录

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
#define eps (1e-12)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
typedef long double ld;
const int MAXN=1e5+10;
int n;
struct Line{//直线y=kx+b
	ld k,b;
}segments[MAXN];
ld f(int x,int idx){//计算点在线段上的值
	return segments[idx].k*ld(x)+segments[idx].b;
}
int cnt;//线段数量
struct LiChao_SegmentTree{
#define lc (p<<1)
#define rc ((p<<1)|1)
	int tr[200000];
	void add(int x0,int y0,int x1,int y1){//添加线段
		if(x0==x1){//点
			segments[++cnt]={0,ld(max(y0,y1))};
		}
		else{
			segments[++cnt]={ld(y1-y0)/ld(x1-x0),y1-ld(y1-y0)/ld(x1-x0)*ld(x1)};//计算斜率/截距
		}
	}
	int cmp(int idx1,int idx2,int x){//比较哪个线段在x更优
		ld y1=f(x,idx1),y2=f(x,idx2);
		if(y2-y1>eps) return 1;
		else if(y1-y2>eps) return -1;
		else return 0;
	}
	void init(){
		segments[0]={0,0};
		memset(tr,0,sizeof(tr));
	}
	void update(int p,int l,int r,int idx){//向下更新各个线段
		int &old=tr[p],mid=(l+r)>>1;
		int res=cmp(old,idx,mid);
		if(res||(!res&&old>idx)){//新线段更优
			swap(old,idx);
		}
		if(l==r){
			return ;
		}
		int resl=cmp(old,idx,l);
		int resr=cmp(old,idx,r);
		if(resl||(!resl&&old>idx)){
			update(lc,l,mid,idx);
		}
		if(resr||(!resr&&old>idx)){
			update(rc,mid+1,r,idx);
		}
	}
	void find_segment(int p,int l,int r,int L,int R,int idx){//寻找线段完全覆盖的区间
		if(l>=L&&r<=R){
			update(p,l,r,idx);
			return;
		}
		int mid=(l+r)>>1;
		if(mid>=L)
			find_segment(lc,l,mid,L,R,idx);
		if(mid<R)
			find_segment(rc,mid+1,r,L,R,idx);
	}
	int query(int p,int l,int r,int idx){//在包含idx的每一个区间里找线段比较
		if(l==r){
			return tr[p];
		}
		int mid=(l+r)>>1;
		int res1=(mid>=idx?query(lc,l,mid,idx):query(rc,mid+1,r,idx));
		int res=cmp(res1,tr[p],idx);
		return (res==1||(!res&&tr[p]<res1)?tr[p]:res1);
	}
#undef lc
#undef rc
};
LiChao_SegmentTree lcst;
int lastans=0;
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	lcst.init();
	for(int i=1;i<=n;++i){
		int opt;
		cin>>opt;
		if(opt==0){
			int k;
			cin>>k;
			int x=(k+lastans-1)%39989+1;
			lastans=lcst.query(1,1,39989,x);
			cout<<lastans<<endl;
		}
		else{
			int x0,y0,x1,y1;
			cin>>x0>>y0>>x1>>y1;
			x0=(x0+lastans-1)%39989+1;
			x1=(x1+lastans-1)%39989+1;
			y0=(y0+lastans-1)%1000000000+1;
			y1=(y1+lastans-1)%1000000000+1;
			if(x1<x0){
				swap(x0,x1),swap(y0,y1);
			}
			lcst.add(x0,y0,x1,y1);
			lcst.find_segment(1,1,39989,x0,x1,cnt);
		}
	}
	return 0;
}