传送门
题意简述：要求支持两种操作：
- 插入一条线段。
- 询问与直线x=kx=kx=k相交的线段中，交点最靠上的线段的编号。
思路：
直接上李超线段树即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
typedef double db;
const int mod=1e9+7,N=40005,M=100005;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct Line{int l,r,id;db k,b;}a[M];
const db eps=1e-6;
inline bool check(const int&x,const int&y,const int&z){
if(!x)return 1;
double t1=a[x].k*z+a[x].b,t2=a[y].k*z+a[y].b;
return fabs(t1-t2)<=eps?x<y:t1<t2;
}
inline double calc(int x,int y){return (a[y].b-a[x].b)/(a[x].k-a[y].k);}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
int id[N<<2];
inline void change(int p,int l,int r,int k){
if(!id[p])id[p]=k;
int l1=id[p],l2=k;
if(check(l1,l2,l))swap(l1,l2);
if(l==r||fabs(a[l1].k-a[l2].k)<=eps){id[p]=l1;return;}
db x=calc(l1,l2);
if(x<l||x>r){id[p]=l1;return;}
if(x<=mid)return id[p]=l2,change(lc,l,mid,l1);
return id[p]=l1,change(rc,mid+1,r,l2);
}
inline void update(int p,int l,int r,int k){
if(a[k].l<=l&&r<=a[k].r)return change(p,l,r,k);
if(a[k].r<=mid)update(lc,l,mid,k);
else if(a[k].l>mid)update(rc,mid+1,r,k);
else update(lc,l,mid,k),update(rc,mid+1,r,k);
}
inline int query(int p,int l,int r,int k){
if(l==r)return id[p];
int ret=k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k);
return check(ret,id[p],k)?id[p]:ret;
}
}
int main(){
for(ri lastans=0,cnt=0,a0,a1,b0,b1,tt=read(),op;tt;--tt){
op=read();
if(!op)a0=(read()+lastans-1)%39989+1,cout<<(lastans=SGT::query(1,1,40000,a0))<<'\n';
else{
a0=(read()+lastans-1)%39989+1;
b0=(read()+lastans-1)%1000000000+1;
a1=(read()+lastans-1)%39989+1;
b1=(read()+lastans-1)%1000000000+1;
if(a0>a1)swap(a0,a1),swap(b0,b1);
if(a0==a1)++cnt,a[cnt]=(Line){a0,a1,cnt,0,max(b0,b1)};
else ++cnt,a[cnt]=(Line){a0,a1,cnt,(db)(b0-b1)/(db)(a0-a1),(db)((ll)a0*b1-(ll)a1*b0)/(db)(a0-a1)};
SGT::update(1,1,40000,cnt);
}
}
return 0;
}