萌新求助挂三个点

提交记录

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define lc(x) tree[x].l
#define rc(x) tree[x].r
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define bh(x) tree[x].bh
#define md(x,y) ((x+y)>>1)
#define mod 39989
#define int long long
using namespace std;
int n,flag,k,cntbh,nowb,xa[100005],ya[100005],xb[100005],yb[100005],lastans;
double nowmax,eps=1e-15;
struct tree
{
    int l,r;
    int bh;
}tree[200005];
inline int read()
{
    int now=0,nev=1; char c=getchar();
    while(c<'0' || c>'9') { if(c=='-') nev=-1; c=getchar();}
    while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return now*nev;
}
double calc(int x,int y)
{
    if(xa[x]==xb[x])
    {
        return max(ya[x],yb[x]);
    }
    return ya[x]+(double)((double)y-(double)xa[x])/double((double)xb[x]-(double)xa[x])*(double)((double)yb[x]-(double)ya[x]);
}
void build(int x,int y,int p)
{
    lc(p)=x; rc(p)=y;
    if(x==y) return;
    int mid=md(x,y);
    build(x,mid,ls(p));
    build(mid+1,y,rs(p));
}
void add(int nowbh,int p)
{
    int mid=md(lc(p),rc(p)),bhnow=nowbh;
    if(lc(p)>=xa[bhnow]&&rc(p)<=xb[bhnow])
    {
        if(calc(bhnow,mid)-calc(bh(p),mid)>eps||(abs(calc(bhnow,mid)-calc(bh(p),mid))<=eps&&bhnow<bh(p))) swap(bhnow,bh(p));
        if(calc(bhnow,lc(p))-calc(bh(p),lc(p))>eps||(abs(calc(bhnow,lc(p))-calc(bh(p),lc(p)))<=eps&&bhnow<bh(p))) add(bhnow,ls(p));
        if(calc(bhnow,rc(p))-calc(bh(p),rc(p))>eps||(abs(calc(bhnow,rc(p))-calc(bh(p),rc(p)))<=eps&&bhnow<bh(p))) add(bhnow,rs(p));
        return;
    }
    if(mid>=xa[bhnow]) add(bhnow,ls(p));
    if(mid<xb[bhnow]) add(bhnow,rs(p));
}
void ask(int x,int p)
{
    int cc=calc(bh(p),x),mid=md(lc(p),rc(p));
    if(cc-nowmax>eps||(abs(cc-nowmax)<=eps&&bh(p)<nowb)) nowmax=cc,nowb=bh(p);
    if(lc(p)==rc(p)) return;
    if(mid>=x) ask(x,ls(p));
    else ask(x,rs(p));
}
signed main()
{
    n=read();
    xa[0]=0;
    xb[0]=39989;
    ya[0]=0;
    yb[0]=0;
    build(1,39989,1);
    for(int i=1;i<=n;i++)
    {
        flag=read();
        if(flag==0)
        {
            nowmax=0; nowb=0;
            k=(read()+lastans-1)%mod+1;
            ask(k,1);
            printf("%d\n",nowb);
            lastans=nowb;
        }
        else
        {
            cntbh++;
            xa[cntbh]=(read()+lastans-1)%mod+1; ya[cntbh]=(read()+lastans-1)%1000000000+1;
            xb[cntbh]=(read()+lastans-1)%mod+1; yb[cntbh]=(read()+lastans-1)%1000000000+1;
            if(xa[cntbh]>xb[cntbh])
            {
                swap(xa[cntbh],xb[cntbh]);
                swap(ya[cntbh],yb[cntbh]);
            }
            add(cntbh,1);
        }
    }
}