李超线段树WA10求调

#include<bits/stdc++.h>
#define int long long
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define pii  pair<double,int>
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,Mod=998244353;
const double eps=1e-6;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
//inline void Add(int &x,int y){(x=x+y+Mod)%Mod;}
//typedef __int128_t i128;
//i128 _base=1;
//inline int mol(int x){return x-Mod*(_base*x>>64);}
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?-x:x;
}
struct Line{
    double k,b;
    int id;
    Line(double k=0,double b=0,int id=0):k(k),b(b),id(id){}
    inline double calx(double x){return k*x+b;}
    inline double calc(Line x){
//      if(k==-1&&x.k==-1)return -1;
//      if(k==-1) return x.calx(b);
//      if(x.k==-1)return calx(x.b);
        return (x.b-b)/(k-x.k);
    } 
};
int cnt;
struct SegTree{
    int l,r,L,R;
    Line x;
    bool flag;
    SegTree(int l,int r,int L,int R,Line x,bool flag):l(l),r(r),L(L),R(R),x(x),flag(flag){}
    SegTree(){}
}tr[N];
inline void updata(int &x,int l,int r,int L,int R,Line k){
    if(!x) {
        x=++cnt;
        tr[x]={0,0,l,r,Line(),false};
    } 
    if(L<=l&&r<=R){
        double l1=tr[x].x.calx(l),r1=tr[x].x.calx(r);
        double l2=k.calx(l),r2=k.calx(r);
        if(!tr[x].flag){
            tr[x].x=k;
            tr[x].flag=1;
        }
        else if(l2-l1>eps&&r2-r1>eps) tr[x].x=k;
        else if(l2-l1>eps||r2-r1>eps){
            int mid=(l+r)>>1;
            if(k.calx(mid)-tr[x].x.calx(mid)>eps) swap(tr[x].x,k);
            if(k.calx(l)>l1) updata(ls(x),l,mid,L,R,k);
            else updata(rs(x),mid+1,r,L,R,k);
        }
    }
    else{
        int mid=(l+r)>>1;
        if(L<=mid) updata(ls(x),l,mid,L,R,k);
        if(R>mid) updata(rs(x),mid+1,r,L,R,k);
    }
}
pii query(int x,int l,int r,int k){
    if(!x) {
        x=++cnt;
        tr[x]={0,0,l,r,Line(),false};
    } 
    double ans=tr[x].x.calx(k);
    int id=tr[x].x.id;
    if(l==r) return make_pair(ans,id);
    int mid=(l+r)>>1;
    if(k<=mid){
        pii ll=query(ls(x),l,mid,k);
        if(ll.first>ans||(fabs(ll.first-ans)<eps&&ll.second<id))
            ans=ll.first,id=ll.second;
    }
    else{
        pii rr=query(rs(x),mid+1,r,k);
        if(rr.first>ans||(fabs(rr.first-ans)<eps&&rr.second<id))
            ans=rr.first,id=rr.second;
    }
    return make_pair(ans,id);
}
inline Line getkb(int x,int y,int xx,int yy,int id){
    if(x==xx){
        return Line{0,max(y,yy),id};
    }
    double k=1.0*(y-yy)/(x-xx),b=y-1.0*k*x;
    return Line{k,b,id};
}
signed main(){
    //_base=(_base<<64)/Mod;
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    int Q=read();
    int lstans=0;
    int tot=0;
    int rt=0;
    while(Q--){
        int op=read();
        if(op==0){
            int k=read();
            k=(k+lstans-1)%39989+1;
            printf("%lld\n",lstans=query(rt,0,100000,k).second);
        }
        else{
            int x=read(),y=read(),xx=read(),yy=read();
            xx=(xx+lstans-1)%39989+1;
            x=(x+lstans-1)%39989+1;
            yy=(yy+lstans-1)%1000000000+1;
            y=(y+lstans-1)%1000000000+1;
            updata(rt,0,100000,min(x,xx),max(xx,x),getkb(x,y,xx,yy,++tot));
        }
    }
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}