LiChaoTree subtask1只过#9求条，玄关

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=3e5+5;
const double eps=1e-9;
int T,ans=0,tot=0;
struct line {
    double k,b;
    int id;
    double val(int x) {return k*x+b;}
};
struct segtree {int l,r;line val;}t[N<<2];
int cmp(double a,double b) {
    if(a-b>eps) return 1;
    if(b-a>eps) return -1;
    return 0;
}
line turn(int x_0,int y_0,int x_1,int y_1,int id) {
    line ans;
    if(x_0==x_1) ans.k=0.0,ans.b=1.0*y_1;
    else ans.k=1.0*(y_1-y_0)/(x_1-x_0),ans.b=1.0*y_0-ans.k*x_0;
    ans.id=id;
    return ans;
}
void build_tree(int l,int r,int id) {
    t[id].l=l,t[id].r=r,t[id].val=(line){0.0,INT_MIN,0};
    if(l==r) return;
    int mid=l+r>>1;
    build_tree(l,mid,id*2),build_tree(mid+1,r,id*2+1);
}
pair<double,int> query(int x,int id) {
    pair<double,int> w=make_pair(t[id].val.val(x),t[id].val.id);
    if(t[id].l==t[id].r) return w;
    int mid=t[id].l+t[id].r>>1;
    if(x<=mid) {
        pair<double,int> tmp=query(x,id*2);
        if(cmp(tmp.first,w.first)==1||(cmp(tmp.first,w.first)==0&&tmp.second<w.second)) return tmp;
        else return w;
    } else {
        pair<double,int> tmp=query(x,id*2+1);
        if(cmp(tmp.first,w.first)==1||(cmp(tmp.first,w.first)==0&&tmp.second<w.second)) return tmp;
        else return w;
    }
}
void modify(int l,int r,line w,int id) {
    int mid=l+r>>1;
    int bmid=cmp(w.val(mid),t[id].val.val(mid));
    if(bmid==1||(bmid==0&&w.id<t[id].val.id)) swap(t[id].val,w);
    int bl=cmp(w.val(l),t[id].val.val(l)),br=cmp(w.val(r),t[id].val.val(r));
    if(bl==1||(bl==0&&w.id<t[id].val.id)) modify(l,r,w,id*2);
    if(br==1||(br==0&&w.id<t[id].val.id)) modify(l,r,w,id*2+1);
}
void Modify(int l,int r,line w,int id) {
    if(t[id].l>=l&&t[id].r<=r) {
        modify(t[id].l,t[id].r,w,id);
        return;
    }
    if(t[id].r<l||t[id].l>r) return;
    Modify(l,r,w,id*2),Modify(l,r,w,id*2+1);
}
void decode(int &x_0,int &y_0,int &x_1,int &y_1) {
    x_0=(x_0+ans-1)%39989+1,x_1=(x_1+ans-1)%39989+1;
    y_0=(y_0+ans-1)%1000000000+1,y_1=(y_1+ans-1)%1000000000+1;
}
int main() {
    cin>>T;
    build_tree(1,39989,1);
    while(T--) {
        int op;
        cin>>op;
        if(op==0) {
            int x;
            cin>>x;
            x=(x+ans-1)%39989+1;
            cout<<(ans=query(x,1).second)<<endl;
        } else {
            int x_0,y_0,x_1,y_1;
            cin>>x_0>>y_0>>x_1>>y_1;
            decode(x_0,y_0,x_1,y_1);
            if(x_0>x_1) swap(x_0,x_1),swap(y_0,y_1);
            if(x_0==x_1&&y_0>y_1) swap(y_0,y_1);
            line w=turn(x_0,y_0,x_1,y_1,++tot);
            Modify(x_0,x_1,w,1);
        }
    }
    return 0;
}