李超线段树

zuytong · 2021-11-17 22:04:52 · 个人记录

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
inline int reads()
{
    int sign=1,re=0; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') sign=-1; c=getchar();}
    while('0'<=c&&c<='9'){re=re*10+(c-'0'); c=getchar();}
    return sign*re;
}
double K[100005],B[100005];
int t[100000<<2|5],cnt;
double y(int id,double x){return K[id]*x+B[id];}
double inter(int id1,int id2){return (B[id2]-B[id1])/(K[id1]-K[id2]);}
int n,ans;
double ansy;
int op,X0,Y0,X1,Y1;
void add(int now,int l,int r,int id,int L,int R)
{
    int mid=(l+r)>>1;
    if(L<=l&&r<=R)
    {
        if(!t[now]){t[now]=id; return;}
        double ogl=y(t[now],l),ogr=y(t[now],r),psl=y(id,l),psr=y(id,r);//og->origin,ps->present
        if(ogl>=psl&&ogr>=psr) return;
        if(ogl<=psl&&ogr<=psr){t[now]=id; return;}
        double cross=inter(id,t[now]);
        if(psl>=ogl)
        {
            if(cross<=mid) add(ls,l,mid,id,L,R);
            else add(rs,mid+1,r,t[now],L,R),t[now]=id;
        }
        else
        {
            if(cross<=mid) add(ls,l,mid,t[now],L,R),t[now]=id;
            else add(rs,mid+1,r,id,L,R);
        }
        return;
    }
    if(L<=mid) add(ls,l,mid,id,L,R);
    if(mid<R) add(rs,mid+1,r,id,L,R);
}
void query(int now,int l,int r,int x)
{
    if(t[now])
    {
        double nowy=y(t[now],x);
        if(nowy>ansy) ansy=nowy,ans=t[now];
        if(nowy==ansy&&ans>t[now]) ans=t[now];
    }
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) query(ls,l,mid,x);
    if(mid<x) query(rs,mid+1,r,x);
}
int main()
{
    freopen("lc.out","w",stdout);
    n=reads();
    while(n--)
    {
        op=reads();
        if(!op)
        {
            X0=reads(); X0=(X0+ans-1)%39989+1;
            ansy=0.0; ans=0;
            query(1,1,39989,X0);
            printf("%d\n",ans);
        }
        else
        {
            X0=reads(); Y0=reads(); X1=reads(); Y1=reads();
            X0=(X0+ans-1)%39989+1; Y0=(Y0+ans-1)%1000000000+1; X1=(X1+ans-1)%39989+1; Y1=(Y1+ans-1)%1000000000+1;
            if(X0>X1) swap(X0,X1),swap(Y0,Y1);
            cnt++;
            if(X0==X1) B[cnt]=max((double)(Y0),(double)(Y1));
            else K[cnt]=(double)(Y1-Y0)/(double)(X1-X0),B[cnt]=(double)(Y0)-(double)(X0)*K[cnt];
            add(1,1,39989,cnt,X0,X1);
        }
    }
    return 0;
}