锐客网

  1. 首页 > it技术 > >

K-Dtree|[Bzoj2716/2648]天使玩偶/SJY摆棋子

#替罪羊树K-Dtree

题意:平面上有一些点,之后还会在平面上插入一些点,还会询问某一个点到平面中最近的点的距离
【K-Dtree|[Bzoj2716/2648]天使玩偶/SJY摆棋子】 K?DtreeK ? D t r e e ,最近的点像 [SDOI2010]Hide[ S D O I 2010 ] H i d eanda n dSeekS e e k 这样求就好了
然后这题是带插入的,和平衡树一样,可能会被卡掉
然而 K?DtreeK ? D t r e e 又不能旋转,所以只能像替罪羊树那样重构了
然后不会 K?DtreeK ? D t r e e 的看这里,再看这里,这个太长了,感觉将就着看吧

#include #define fp(i,a,b) for(register int i=a,I=b+1; iI; --i) #define go(u) for(register int i=fi[u],v=e[i].to; i; v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) templateinline bool cmax(T&a,const T&b){return ainline bool cmin(T&a,const T&b){return a>b?a=b,1:0; } using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++; } templateinline void sd(T&x){ char c; T y=1; while(c=gc(),(c<48||57inline void we(T x){ if(C>1<<20)Ot(); if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z); sr[++C]='\n'; } const int N=5e5+5,M=2*N,inf=-1u>>1; const double alpha=.77; typedef int arr[N]; int n,m,rt,D,ans,cb,cn,tot,bin[M]; struct po{ int d[2],mi[2],mx[2],l,r,sz; inline int&operator[](int x){return d[x]; } inline void clr(){fp(i,0,1)mi[i]=mx[i]=d[i]; l=r=0,sz=1; } inline bool operator<(po b)const{return d[D]>1,p=New(); D=k; nth_element(a+L,a+mid,a+R+1); tr[p]=a[mid]; lc=Ltr[p].sz*alpha||tr[rc].sz>tr[p].sz*alpha) return tot=0,cle(p),p=build(1,tot,k),void(); if(t[k]

    推荐阅读


    上一篇：2-2.【书本阅读】――最强大脑忆菲冲天

    下一篇：dsPIC33F之PWM1 Interrupt