萌新求助李超树

myee @ 2021-11-10 10:31:43

by myee @ 2021-11-10 10:32:01

代码

// Li-Chao 树真香（雾）
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
typedef std::pair<llt,uint>Pair;
const dbl eps=1e-9;
dbl feq(dbl a,dbl b){return a+eps>b&&a<b+eps;}
struct Line
{
    dbl k,b;uint num;
    Line(dbl k=0,dbl b=-3e9,uint num=-1):k(k),b(b),num(num){}
    dbl val(uint x){return k*x+b;}
    friend bol Greater(Line a,Line b,uint x){return feq(a.val(x),b.val(x))?a.num<b.num:(a.val(x)+eps>b.val(x));}
    friend Line merge(Line a,Line b,uint x){return Greater(a,b,x)?a:b;}
};
struct Seg
{
    Seg*L,*R;uint len,from;Line Best;
    voi build(uint l,uint r){if((len=r-(from=l))>1)L=new Seg,R=new Seg,L->build(l,l+(len>>1)),R->build(l+(len>>1),r);}
    voi insert(uint l,uint r,Line line)
    {
        if(!l&&r==len)
        {
            // printf("[%u,%u):y=%.2lfx+%.2lf\n",from+l,from+r,line.k,line.b);
            uint mid=from+(len>>1);
            if(len>1)((Best.k<line.k)==Greater(line,Best,mid))?L->insert(0,len>>1,line):R->insert(0,len-(len>>1),line);
            Best=merge(line,Best,mid);
            return;
        }
        if(l<(len>>1))
            if(r<=(len>>1))L->insert(l,r,line);
            else L->insert(l,len>>1,line),R->insert(0,r-(len>>1),line);
        else R->insert(l-(len>>1),r-(len>>1),line);
    }
    Line find(uint p){return(len==1)?Best:merge((p<(len>>1)?L->find(p):R->find(p-(len>>1))),Best,p+from);}
};
Seg S;
int main()
{
    S.build(0,100000);
    uint n,ans=0,cnt=0,op,k,x0,x1,y0,y1;
    scanf("%u",&n);
    while(n--)
    {
        scanf("%u",&op);
        if(op)
        {
            scanf("%u%u%u%u",&x0,&y0,&x1,&y1);
            x0=(x0+ans-1)%39989+1,x1=(x1+ans-1)%39989+1,y0=(y0+ans-1)%1000000000+1,y1=(y1+ans-1)%1000000000+1;
            if(x0>x1)std::swap(x0,x1),std::swap(y0,y1);
            Line line((x0==x1?0.:((dbl)y1-y0)/(x1-x0)),(x0==x1?(dbl)std::max(y0,y1):(dbl)y0-((dbl)y1-y0)/(x1-x0)*x0),cnt++);
            // printf("%u:y=%.2lfx+%.2lf\n",cnt,line.k,line.b);
            S.insert(x0,x1+1,line);
        }
        else scanf("%u",&k),k=(k+ans-1)%39989+1,printf("%u\n",ans=S.find(k).num+1);
    }
    return 0;
}

by myee @ 2021-11-10 11:56:59

人傻了，挂在

if(len>1)((Best.k<line.k)==Greater(line,Best,mid))?L->insert(0,len>>1,line):R->insert(0,len-(len>>1),line);

by MatrixCascade @ 2021-11-10 12:28:06

by Butterfly__qwq @ 2022-04-24 11:35:15

@myee 《红名萌新》《会写李超树的萌新》