bzoj3815: 卡常数

随机数据，带修改，求到空间中到给定点距离为给定值的点的编号，唯一解。

建三维kdtree，对查询用可行性剪枝在树上找，由于数据随机，插入删除时不需要维护平衡。

#include<bits/stdc++.h>

using namespace std;

typedef double ld;

const ld _0=1e-;

int n,m,res;

ld _a,_b,la=0.1,X[],R;

void mins(ld&a,ld b){if(a>b)a=b;}

void maxs(ld&a,ld b){if(a<b)a=b;}

ld f(ld x){return x=la*x+,_a*x-_b*sin(x);}

void $(ld&x){

    ld L=-,R=;

    while(R-L>1e-){

        ld M=(L+R)*.;

        f(M)<x?L=M:R=M;

    }

    x=(L+R)*.;

}

char ib[],*ip=ib;

int _(){

    int x=;

    while(*ip<)++ip;

    while(*ip>)x=x*+*ip++-;

    return x;

}

ld _Lf(){

    ld x=;

    bool f=;

    while(*ip<)*ip++=='-'?f=:;

    while(*ip>)x=x*+(*ip++-);

    if(*ip=='.'){

        ld a=.;

        for(++ip;*ip>;x+=(*ip++-)*a,a*=.);

    }

    return f?-x:x;

}

ld max(ld a,ld b){return a>b?a:b;}

ld near(ld x,ld l,ld r){return x<l?l-x:max(x-r,);}

ld far(ld x,ld l,ld r){return max(r-x,x-l);}

ld dis(ld a,ld b,ld c){return a*a+b*b+c*c;}

struct node{

    node*c[],*f;

    ld x[],mn[],mx[];

    int id;

    bool chk1(){

        return this

        && dis(near(X[],mn[],mx[]),near(X[],mn[],mx[]),near(X[],mn[],mx[]))<R+_0

        && dis( far(X[],mn[],mx[]), far(X[],mn[],mx[]), far(X[],mn[],mx[]))>R-_0;

    }

    bool chk2(){

        return id&&fabs(dis(x[]-X[],x[]-X[],x[]-X[])-R)<_0;

    }

    void init(int ID,bool d){

        id=ID;

        for(int i=;i<;++i){

            x[i]=_Lf();

            if(d)$(x[i]);

            mn[i]=mx[i]=x[i];

        }

    }

    void up(){

        if(id)for(int i=;i<;++i)mn[i]=mx[i]=x[i];

        else for(int i=;i<;++i)mn[i]=1e10,mx[i]=-1e10;

        for(int i=;i<;++i)if(c[i]){

            c[i]->f=this;

            if(c[i]->mn[]>c[i]->mx[])c[i]=;

            else for(int j=;j<;++j){

                mins(mn[j],c[i]->mn[j]);

                maxs(mx[j],c[i]->mx[j]);

            }

        }

    }

}ns[],*np=ns,*rt,*nr[];

int D=;

bool operator<(const node&a,const node&b){

    return a.x[D]<b.x[D];

}

node*build(node*l,node*r){

    if(l==r)return ;

    node*m=l+(r-l>>);

    nth_element(l,m,r);

    D=(D+)%;

    m->c[]=build(l,m);

    m->c[]=build(m+,r);

    m->up();

    D=(D+)%;

    return m;

}

void ins(node*w,node*a,int D){

    int d=a->x[D]>w->x[D];

    if(w->c[d])ins(w->c[d],a,(D+)%);

    else w->c[d]=a;

    w->up();

}

bool find(node*w){

    if(!w->chk1())return ;

    if(w->chk2())return res=w->id,;

    return find(w->c[])||find(w->c[]);

}

int main(){

    fread(ib,,sizeof(ib),stdin);

    n=_(),m=_(),_a=_Lf(),_b=_Lf();

    for(int i=;i<=n;++i)np++->init(i,);

    rt=build(ns,np);

    for(node*a=ns;a!=np;++a)nr[a->id]=a;

    while(m--){

        int op=_();

        if(op){

            X[]=_Lf();

            X[]=_Lf();

            X[]=_Lf();

            R=_Lf();

            $(X[]),$(X[]),$(X[]),$(R);

            R*=R;

            find(rt);

            la=res;

            printf("%d\n",res);

        }else{

            ld _id=_Lf();

            $(_id);

            int id=round(_id);

            node*u=nr[id];

            for(u->id=;u;u->up(),u=u->f);

            np->init(id,);

            ins(rt,nr[id]=np++,);

        }

    }

    return ;

}