题意：
两种操作，插入一个线段或询问 x=x0 x = x 0 时最大y对应的线段编号，同样大输出最小
思路：
刚刚学了李超树就来A一下板子题，比起之前的1568多了很多细节。
首先，我们需要确定线段的更新区间，我们更新只能在这个区间更新，其次，为了编号以及精度更高，我是用的是很多个区间去存的线段信息。其他方面跟1568大同小异，但是要注意斜率不存在的线段以及同等价值优先编号最小
错误及反思：
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 50100;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps=1e-6;
int segx1[N<<2],segy1[N<<2],segid[N<<2],segx2[N<<2],segy2[N<<2];int ans=0,lastans=0,tid=0;
bool did[N<<2];
double tval;double Getval(int tx,int xx0,int yy0,int xx1,int yy1)
{if(xx0==xx1) return yy1;return 1.0*(tx-xx1)*(yy0-yy1)/(xx0-xx1)+yy1;
}void change(int x,int v,int id,int l,int r,int rt){if(l==r){if(!did[rt]){segx1[rt]=segx2[rt]=l;segy1[rt]=segy2[rt]=v;segid[rt]=id;did[rt]=true;}else{double tx=Getval(x,segx1[rt],segy1[rt],segx2[rt],segy2[rt]);if(tx>v||tx==v&&id<segid[rt]){segx1[rt]=segx2[rt]=l;segy1[rt]=segy2[rt]=v;segid[rt]=id;}}return ;}int m=l+r>>1;if(m>=x) change(x,v,id,lson);else change(x,v,id,rson);
}double Inter(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{double a=x2-x1;double b=x3-x4;double c=y2-y1;double d=y3-y4;double g=x3-x1;double h=y3-y1;double f=a*d-b*c;double t=(d*g-b*h)/f;double s=(-c*g+a*h)/f;return x1+t*(x2-x1);
}void update(int L,int R,int xx0,int yy0,int xx1,int yy1,int id,int l,int r,int rt){if(L<=l&&R>=r){if(!did[rt])segx1[rt]=xx0,segy1[rt]=yy0,segx2[rt]=xx1,segy2[rt]=yy1,segid[rt]=id,did[rt]=true;else{double f1=Getval(l,xx0,yy0,xx1,yy1);double f2=Getval(l,segx1[rt],segy1[rt],segx2[rt],segy2[rt]);double f3=Getval(r,xx0,yy0,xx1,yy1);double f4=Getval(r,segx1[rt],segy1[rt],segx2[rt],segy2[rt]);if(f1<=f2&&f3<=f4) return ;else if(f1>=f2&&f3>=f4)segx1[rt]=xx0,segy1[rt]=yy0,segx2[rt]=xx1,segy2[rt]=yy1,segid[rt]=id;else{int m=l+r>>1;double len=Inter(xx0,yy0,xx1,yy1,segx1[rt],segy1[rt],segx2[rt],segy2[rt]);if(f1>=f2){if(len<=m) update(L,R,xx0,yy0,xx1,yy1,id,lson);else{update(L,R,segx1[rt],segy1[rt],segx2[rt],segy2[rt],segid[rt],rson);segx1[rt]=xx0; segy1[rt]=yy0; segx2[rt]=xx1; segy2[rt]=yy1; segid[rt]=id;}}else{if(len>m)update(L,R,xx0,yy0,xx1,yy1,id,rson);else{update(L,R,segx1[rt],segy1[rt],segx2[rt],segy2[rt],segid[rt],lson);segx1[rt]=xx0; segy1[rt]=yy0; segx2[rt]=xx1; segy2[rt]=yy1; segid[rt]=id;}}}}return ;}int m=l+r>>1;if(L<=m) update(L,R,xx0,yy0,xx1,yy1,id,lson);if(R>m) update(L,R,xx0,yy0,xx1,yy1,id,rson);
}void query(int x,int l,int r,int rt){if(did[rt]){double tx=Getval(x,segx1[rt],segy1[rt],segx2[rt],segy2[rt]);if(tx>tval||tx==tval&&segid[rt]<ans){tval=tx;ans=segid[rt];}}if(l==r) return ;int m=l+r>>1;if(m>=x) query(x,lson);else query(x,rson);
}int main(){int m; scanf("%d",&m);while(m--){int t; scanf("%d",&t);if(t){int xx0,yy0,xx1,yy1;scanf("%d%d%d%d",&xx0,&yy0,&xx1,&yy1);xx0=(xx0+lastans-1)%39989+1;yy0=(yy0+lastans-1)%1000000000+1;xx1=(xx1+lastans-1)%39989+1;yy1=(yy1+lastans-1)%1000000000+1;if(xx0>xx1) swap(xx0,xx1),swap(yy0,yy1);if(xx0==xx1) change(xx0,max(yy0,yy1),++tid,1,50000,1);else update(xx0,xx1,xx0,yy0,xx1,yy1,++tid,1,50000,1);}else{int x;scanf("%d",&x);x=(x+lastans-1)%39989+1;ans=0; tval=0;query(x,1,50000,1);printf("%d\n",ans);lastans=ans;}}
}