李超线段树80pts求调

#include<bits/stdc++.h>
using namespace std;
#define double long double

namespace acac
{
    struct node
    {
        double b,k;
    }line[100010];
    int tree[400010];
    int cnt;

    const int mod2=1e9,mod=39989;
    const double eps=1e-12;

    int cmp(double a,double b)
    {
        if(fabs(a-b)<=eps)return 0;
        return (a<b)?-1:1;
    }

    double calc(node a,double x)
    {
        return a.b+x*a.k;
    }

    void add(double x1,double y1,double x2,double y2)
    {
        cnt++;
        if(!cmp(x1,x2))
        {
            line[cnt].b=max(y1,y2);
            line[cnt].k=0;
            return ;
        }
        line[cnt].k=(y2-y1)/(x2-x1);
        line[cnt].b=y1-x1*line[cnt].k;
    }
    void update(int u,int l,int r,int w)
    {
        int mid=(l+r)>>1;
        int tf=cmp(calc(line[w],mid),calc(line[tree[u]],mid));
        if(tf>0||(!tf&&w<tree[u]))swap(w,tree[u]);
        int tl=cmp(calc(line[w],l),calc(line[tree[u]],l)),tr=cmp(calc(line[w],r),calc(line[tree[u]],r));
        if(tl>0||(!tl&&w<tree[u]))update(2*u,l,mid,w);
        if(tr>0||(!tr&&w<tree[u]))update(2*u+1,mid+1,r,w);
    }
    void c(int u,int l,int r,int L,int R,int w)
    {
        if(l>R||L>r)return ;
        if(L<=l&&R>=r)
        {
            update(u,l,r,w);
            return ;
        }
        int mid=(l+r)>>1;
        c(2*u,l,mid,L,R,w); 
        c(2*u+1,mid+1,r,L,R,w); 
    }

    int re,ry;
    void q(int u,int l,int r,int L,int R,int x)
    {
        if(l>R||L>r)return ;
        double y=calc(line[tree[u]],1.0*x);

        int tf=cmp(y,ry);
        if(tf>0||(!tf&&tree[u]<re))
        {
            re=tree[u];
            ry=y;
        }
        if(l==r)return ;
        int mid=(l+r)>>1;
        q(2*u,l,mid,L,R,x);
        q(2*u+1,mid+1,r,L,R,x);
    }

    int main()
    {
        int t,lans=0;
        scanf("%d",&t);
        while(t--)
        {
            int op;
            scanf("%d",&op);
            if(op)
            {
                int x1,x2,y1,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                x1=(x1+lans-1)%mod+1,x2=(x2+lans-1)%mod+1;
                y1=(y1+lans-1)%mod2+1,y2=(y2+lans-1)%mod2+1;
                if(x1>x2)swap(x1,x2),swap(y1,y2);
                add(x1,y1,x2,y2);
                c(1,1,mod,x1,x2,cnt);
            }
            else
            {
                int x;
                scanf("%d",&x);
                x=(x+lans-1)%mod+1;
                re=ry=0;
                q(1,1,mod,x,x,x);
                lans=re;
                cout<<re<<'\n';
            }
        }
        return 0;
    }
}

int main()
{
    acac::main();
    return 0;
}

wa sub1最后两个点
是精度问题吗（