提交记录

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double 
int read()
{
	int now=0,nev=1; 
	char c=getchar();
	while(c<'0' || c>'9') 
	{ 
		if(c=='-') 
			nev=-1; 
		c=getchar();
	}
	while(c>='0' && c<='9') 
	{ 
		now=(now<<1)+(now<<3)+(c&15); 
		c=getchar(); 
	}
	return now*nev;
}
const int MAXN=4e5+10;
const int mod1=39989;
const int mod2=1e9;
const double eps=1e-9;
int n;
int ans=0;
struct line
{
	db k,b;
}p[MAXN];
int calc(int id,int x)//计算平面直角坐标系中x对应的y值 
{
//	cout<<p[id].k<<"*"<<x<<"+"<<p[id].b<<endl;
	return p[id].b+p[id].k*x;
}
int cmp(db x,db y)
{
	if(x-y>eps)
		return 1;
	if(y-x>eps)
		return -1;
	return 0;
}
int s[MAXN<<1];
int tt=0;
typedef pair<db,int>pdi;
pdi pmax(pdi x,pdi 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;
} 
void insert(int x0,int y0,int x1,int y1)//添加直线 
{
	tt++;
	if(x0==x1)//特判直线斜率为0 
	{
		p[tt].k=0;
		p[tt].b=max(y0,y1);
	}
	else
	{
		p[tt].k=1.0*(y1-y0)/(x1-x0);
		p[tt].b=(y0-p[tt].k*x0);
	}
}
void update(int root,int cl,int cr,int u)//将线段完全覆盖到的区间进行修改 
{
	int &v=s[root];
	int mid=cl+cr>>1;
	if(cmp(calc(u,mid),cmp(v,mid))==1)
		swap(u,v);
	int bl=cmp(calc(u,cl),calc(v,cl)),br=cmp(calc(u,cr),calc(v,cr));
	if(bl==1 || (bl==0 && u<v))
		update(root<<1,cl,mid,u);
	if(br==1 || (br==0 && u<v))
		update(root<<1|1,mid+1,cr,u);
}
void modefy(int root,int cl,int cr,int l,int r,int u)
{
	if(l<=cl && cr<=r)
	{
		update(root,cl,cr,u);
		return ;
	}
	int mid=cl+cr>>1;
	if(l<=mid)
		modefy(root<<1,cl,mid,l,r,u);
	if(r>mid)
		modefy(root<<1|1,mid+1,cr,l,r,u);
}
pdi query(int root,int l,int r,int d)
{
	if(l>d || r<d)
		return {0,0};
	int mid=l+r>>1;
	db res=calc(s[root],d);
//	cout<<"+"<<d<<endl;
	if(l==r)
		return {res,s[root]};
	return pmax({res,s[root]},pmax(query(root<<1,l,mid,d),query(root<<1|1,mid+1,r,d)));
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int op;
		op=read();
		if(op==1)
		{
			int x0,y0,x1,y1;
			x0=read(),y0=read(),x1=read(),y1=read();
			x0=(x0+ans-1+mod1)%mod1+1;
			x1=(x1+ans-1+mod1)%mod1+1;
			y0=(y0+ans-1+mod2)%mod2+1;
			y1=(y1+ans-1+mod2)%mod2+1;
			if(x0>x1)
				swap(x0,x1),swap(y0,y1);
			insert(x0,y0,x1,y1);
			modefy(1,1,mod1,x0,x1,tt);
		}
		if(op==0)
		{
			int k;
			k=read();
			k=(k+ans-1+mod1)%mod1+1;
			ans=query(1,1,mod1,k).second;
			printf("%d\n",ans);
		}
	}
	return 0;
}