不管了先贴一个板子上来坑这周六再填。
#include<bits/stdc++.h>
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const int maxt=40000;
const double eps=1e-9;
using mkp=pair<double,int>; // make pair
int cmp(double x,double y){if(x-y>eps) return 1;if(y-x>eps) return -1;return 0;
}
struct line{double k,b;}; // 一次函数斜率和 y 轴截距；
line p[100005];
int s[200005],cnt;
double calc(int id,int d){return p[id].k*d+p[id].b;} // d 为横坐标，id 为线段编号；
void add(int x0,int y0,int x1,int y1){ // 线段起始坐标和结束坐标； cnt++;if(x0==x1) // 特判垂直于 x 轴的情况（没有斜率）； p[cnt].k=0,p[cnt].b=max(y0,y1);elsep[cnt].k=1.0*(y1-y0)/(x1-x0),p[cnt].b=y0-p[cnt].k*x0; // 算斜率和 y 轴截距； return;
}
void merge(int id,int cl,int cr,int u){ // 对线段完全覆盖到的区间进行修改； int &v=s[id],mid=(cl+cr)/2;int bmid=cmp(calc(u,mid),calc(v,mid)); // 计算中点处原直线更靠上还是当前直线更靠上； if(bmid==1||(bmid==0&&u<v)) 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)) merge(id*2,cl,mid,u);if(br==1||(br==0&&u<v)) merge(id*2+1,mid+1,cr,u);return;
}
void update(int id,int cl,int cr,int l,int r,int u){ // 定位插入线段完全覆盖到的区间； if(l<=cl&&cr<=r){merge(id,cl,cr,u);return;}int mid=(cl+cr)/2;if(l<=mid) update(id*2,cl,mid,l,r,u);if(r>mid) update(id*2+1,mid+1,cr,l,r,u);return;
}
mkp pmax(mkp x,mkp y){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;
}
mkp query(int id,int l,int r,int d){ // 查询； if(r<d||d<l) return {0,0}; // 不包含； int mid=(l+r)/2;double res=calc(s[id],d);if(l==r) return {res,s[id]};return pmax({res,s[id]},pmax(query(id*2,l,mid,d),query(id*2+1,mid+1,r,d))); // 那很长了；
}
int main(){int n,lastans=0;scanf("%d",&n);while(n--){int op;scanf("%d",&op);if(op==1){ // 插入； int x0,y0,x1,y1;scanf("%d%d%d%d",&x0,&y0,&x1,&y1);x0=(x0+lastans-1+mod1)%mod1+1,x1=(x1+lastans-1+mod1)%mod1+1;y0=(y0+lastans-1+mod2)%mod2+1,y1=(y1+lastans-1+mod2)%mod2+1; // 恶心人的强制在线； if(x0>x1) swap(x0,x1),swap(y0,y1);add(x0,y0,x1,y1),update(1,1,mod1,x0,x1,cnt);}else{ // 查询； int x;scanf("%d",&x);x=(x+lastans-1+mod1)%mod1+1,lastans=query(1,1,mod1,x).second;printf("%d\n",lastans);}}return 0;
}