同上题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 40000
using namespace std;
long long n,m,type,a,b,c,d,root,tot=,ls[maxn<<],rs[maxn<<],cnt=;
bool flag[maxn<<];
long long ans,lastans=;
double mx=;
struct seg
{
long long x1,y1,x2,y2,id;
seg (long long x1,long long y1,long long x2,long long y2,long long id):x1(x1),y1(y1),x2(x2),y2(y2),id(id) {}
seg () {}
}s[maxn<<];
void build(long long &now,long long left,long long right)
{
now=++tot;
if (left==right) return;
long long mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
double f(seg x,long long pos)
{
double k=(double)(x.y1-x.y2)/(x.x1-x.x2),b=(double)(x.x1*x.y2-x.x2*x.y1)/(x.x1-x.x2);
return k*pos+b;
}
void ask(long long now,long long left,long long right,long long pos)
{
if ((mx<f(s[now],pos)) && (flag[now])) {mx=f(s[now],pos);ans=s[now].id;}
if (left==right) return;
long long mid=(left+right)>>;
if (pos<=mid) ask(ls[now],left,mid,pos);
else ask(rs[now],mid+,right,pos);
}
void pushdown(long long now,long long left,long long right,seg x)
{
long long mid=(left+right)>>;
if (!flag[now]) {flag[now]=true;s[now]=x;return;}
double r1=f(x,mid),r2=f(s[now],mid);
if (left==right) {if (r1>r2) swap(x,s[now]);return;}
double f1=f(x,left),f2=f(s[now],left),f3=f(x,right),f4=f(s[now],right);
if ((f1<f2) && (f3<f4)) return;
if ((f1>f2) && (f3>f4)) {swap(x,s[now]);return;}
if (r1>r2) swap(x,s[now]);
if ((f1>f2)^(r1>r2)) pushdown(ls[now],left,mid,x);
else pushdown(rs[now],mid+,right,x);
}
void modify(long long now,long long left,long long right,long long l,long long r,seg x)
{
if ((left==l) && (right==r))
{
pushdown(now,left,right,x);
return;
}
long long mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r,x);
else if (l>=mid+) modify(rs[now],mid+,right,l,r,x);
else
{
modify(ls[now],left,mid,l,mid,x);
modify(rs[now],mid+,right,mid+,r,x);
}
}
int main()
{
scanf("%lld",&m);n=;
build(root,,n);
for (long long i=;i<=m;i++)
{
scanf("%lld",&type);
if (type==)
{
scanf("%lld",&a);a=(a+lastans-)%+;
mx=;ans=;ask(root,,n,a);
lastans=ans;printf("%lld\n",lastans);
}
else
{
cnt++;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
a=(a+lastans-)%+;b=(b+lastans-)%+;
c=(c+lastans-)%+;d=(d+lastans-)%+;
if (a>c) {swap(a,c);swap(b,d);}
modify(root,,n,a,c,seg(a,b,c,d,cnt));
}
}
return ;
}