李超线段树

// 李超线段树 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const double eps=1e-9;
const int N=100005;
#define M1 39989
#define M2 1000000000
#define ls u<<1
#define rs u<<1|1
typedef pair<double,int> pdi;
int n,cnt,lastans;
struct line{double k,b; //斜率,截距
}p[N];        
int tr[N<<2]; //线段编号int cmp(double a,double b){ //比a,bif(a-b>eps) return 1;if(b-a>eps) return -1;return 0;
}
double Y(int id,int x){ //求Y值return p[id].k*x+p[id].b;
}
void change(int u,int l,int r,int L,int R,int id){ //修改int mid=(l+r)>>1;if(L<=l&&r<=R){int cm=cmp(Y(id,mid),Y(tr[u],mid));if(cm==1||(!cm&&id<tr[u])) swap(id,tr[u]);int cl=cmp(Y(id,l),Y(tr[u],l));if(cl==1||(!cl&&id<tr[u])) change(ls,l,mid,L,R,id);int cr=cmp(Y(id,r),Y(tr[u],r));if(cr==1||(!cr&&id<tr[u])) change(rs,mid+1,r,L,R,id);return;}if(L<=mid) change(ls,l,mid,L,R,id);if(mid<R) change(rs,mid+1,r,L,R,id);
}
pdi pmax(pdi a,pdi b){ //Y值大且编号小if(cmp(a.first,b.first)==1) return a;else if(cmp(a.first,b.first)==-1) return b;else return a.second<b.second ? a : b;
}
pdi query(int u,int l,int r,int x){ //查询if(l==r) return {Y(tr[u],x),tr[u]};int mid=(l+r)>>1;pdi t={Y(tr[u],x),tr[u]};if(x<=mid) return pmax(t,query(ls,l,mid,x));else return pmax(t,query(rs,mid+1,r,x));
}
int main(){int op,x0,y0,x1,y1,x; double k,b;scanf("%d",&n);while(n--){scanf("%d",&op);if(op==1){scanf("%d%d%d%d",&x0,&y0,&x1,&y1);x0=(x0+lastans-1)%M1+1,x1=(x1+lastans-1)%M1+1;y0=(y0+lastans-1)%M2+1,y1=(y1+lastans-1)%M2+1;if(x0>x1) swap(x0,x1),swap(y0,y1);if(x0==x1) k=0,b=max(y0,y1);else k=1.0*(y1-y0)/(x1-x0),b=y0-k*x0;   p[++cnt]={k,b};change(1,1,M1,x0,x1,cnt);}else{scanf("%d",&x);x=(x+lastans-1)%M1+1;lastans=query(1,1,M1,x).second;printf("%d\n",lastans);}}
}