20分求助

#include<bits/stdc++.h>
using namespace std;
int n,op,k,xx0,xx1,yy0,yy1,id,asid;
double kk,bb,ans;
struct dd{
    int bh,lazy;
    double zu,yo,k1,b1;
}shu[4000001];
int bj(double x,double y)
{
    if(x-y>0.0000000001)
      return 1;
    if(y-x>0.0000000001)
      return -1;
    return 0;
}
void dfs(int l,int r,int s)
{
//  cout<<'!'<<xx0<<' '<<xx1<<' '<<l<<' '<<r<<' '<<s<<endl;
    int mid=(l+r)/2;
    if(xx0>r||xx1<l)
      return;
    if(l==r)
    {
        double zb=1.0*kk*l+1.0*bb;
        if(bj(zb,shu[s].zu)==1)
        {
            shu[s].zu=shu[s].yo=zb;
            shu[s].bh=id;
            shu[s].b1=zb;
        }
        return;
    }
    if(l>=xx0&&r<=xx1)
    {
        double zb=1.0*kk*l+1.0*bb,yb=1.0*kk*r+1.0*bb;
//      cout<<s<<' '<<l<<' '<<r<<' '<<zb<<' '<<yb<<' '<<shu[s].zu<<' '<<shu[s].yo<<endl;
        if(bj(zb,shu[s].zu)==1&&bj(yb,shu[s].yo)==1)
        {
            shu[s].zu=zb;
            shu[s].yo=yb;
            shu[s].bh=id;
            shu[s].k1=kk;
            shu[s].b1=bb;
        //  cout<<'!'<<s<<' '<<l<<' '<<r<<' '<<zb<<' '<<yb<<' '<<shu[s].zu<<' '<<shu[s].yo<<endl;
            return;
        }
        if(bj(zb,shu[s].zu)==1)
        {
            if(bj(shu[s].zu+shu[s].yo,zb+yb)==1)
                dfs(l,mid,s*2);else
                {
                    shu[s*2].zu=zb;
                    shu[s*2].yo=1.0*kk*mid+bb;
                    shu[s*2].bh=id;
                    shu[s*2].k1=kk;
                    shu[s*2].b1=bb;
                    dfs(mid+1,r,s*2+1);
                }
        }
        if(bj(yb,shu[s].yo)==1)
        {
            if(bj(shu[s].zu+shu[s].yo,zb+yb)==1)
                dfs(mid+1,r,s*2+1);else
                {
                    shu[s*2+1].zu=1.0*(mid+1)*kk+bb;
                    shu[s*2+1].yo=yb;
                    shu[s*2+1].bh=id;
                    shu[s*2+1].k1=kk;
                    shu[s*2+1].b1=bb;
                    dfs(l,mid,s*2);
                }
        }
    }else 
    {
        if(mid>=xx0)
          dfs(l,mid,s*2);
        if(mid<=xx1)
          dfs(mid+1,r,s*2+1);
    }
}
void cz(int l,int r,int s)
{
//  cout<<l<<' '<<r<<' '<<s<<' '<<asid<<' '<<shu[s].k1<<' '<<shu[s].b1<<' '<<ans<<endl;
    int mid=(l+r)/2;
/*  if(shu[s].lazy!=0)
    {
        shu[s*2].lazy=shu[s*2+1].lazy=shu[s].lazy;
        shu[s*2].bh=shu[s*2+1].bh=shu[s].lazy;
        shu[s*2].zu=shu[s].zu;
        shu[s*2+1].yo=shu[s].yo;
        shu[s*2].yo=shu[s].k1*mid+shu[s].b1;
        shu[s*2+1].zu=shu[s].k1*(mid+1)+shu[s].b1;
        shu[s].lazy=0;  
    }*/
    if(shu[s].bh!=0&&(bj(1.0*shu[s].k1*k+1.0*shu[s].b1,ans)==1||bj(1.0*shu[s].k1*k+1.0*shu[s].b1,ans)==0&&shu[s].bh<asid))
      ans=1.0*shu[s].k1*k+1.0*shu[s].b1,asid=shu[s].bh;
    if(l==r)
    {
    //  ans=shu[s].bh;
        return;
    }
    if(k>mid)
      cz(mid+1,r,s*2+1);else
      cz(l,mid,s*2);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            id++;
            scanf("%d%d%d%d",&xx0,&yy0,&xx1,&yy1);
            xx0=(xx0+asid-1)%39989+1;
            yy0=(yy0+asid-1)%1000000000+1;
            xx1=(xx1+asid-1)%39989+1;
            yy1=(yy1+asid-1)%1000000000+1;
            if(xx0>xx1||xx0==xx1&&yy0<yy1)
              swap(xx0,xx1),swap(yy0,yy1);
            if(xx0==xx1)
            {
                kk=0;
                bb=1.0*max(yy0,yy1);
            }else
            {
                kk=1.0*(yy1-yy0)/(1.0*(xx1-xx0));
                bb=1.0*yy0-1.0*kk*xx0;
            }
            dfs(1,40000,1);
        }else
        {
    //      cout<<'!'<<endl;
            scanf("%d",&k);
            k=(k+asid-1)%39989+1;
            ans=-1.0;
            asid=0;
            cz(1,40000,1);
            printf("%d\n",asid);    
        }
    }
    return 0;
}