因為IOICAMP的judge是暫時性的，所以有人備份了題目
http://codingsimplifylife.blogspot.tw/2016/02/ioi-camp-judge-37_4.html
解法:
CDQ分治不會寫，所以就用老派的kd tree去解吧，這裡提供兩種寫法:
- 第一種寫法是動態的將點進行插入，因為必須要做到動態的插入操作，而一般kd tree不能用旋轉的方式來平衡，所以利用替罪羊樹的概念來平衡。(3.10s)
- 第二種寫法是把所有操作讀入，把所有要插入的點先建成一顆kd tree，接著倒著作回來，如果遇到插入操作就把點從kd tree裡刪除，但是刪除的速度很慢，所以是壓線過的。(7.16)
第一種作法code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | #include<stdio.h> #include<limits.h> //using namespace std; #ifndef SUNMOON_DYNEMIC_KD_TREE #define SUNMOON_DYNEMIC_KD_TREE #include<algorithm> #include<vector> #include<queue> #include<cmath> template<typename T,size_t kd>//kd表示有幾個維度 class kd_tree{ public: struct point{ T d[kd]; inline T dist(const point &x)const{ T ret=0; for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]); return ret; } inline bool operator<(const point &b)const{ return d[0]<b.d[0]; } }; private: struct node{ node *l,*r; point pid; int s; node(const point &p):l(0),r(0),pid(p),s(1){} inline void up(){ s=(l?l->s:0)+1+(r?r->s:0); } }*root; const double alpha,loga; const T INF;//記得要給INF，表示極大值 std::vector<node*> A; int qM; std::priority_queue<std::pair<T,point > >pQ; struct __cmp{ int sort_id; inline bool operator()(const node*x,const node*y)const{ return x->pid.d[sort_id]<y->pid.d[sort_id]; } }cmp; void clear(node *o){ if(!o)return; clear(o->l); clear(o->r); delete o; } inline int size(node *o){ return o?o->s:0; } node* build(int k,int l,int r){ if(l>r)return 0; if(k==kd)k=0; int mid=(l+r)/2; cmp.sort_id=k; std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp); node *ret=A[mid]; ret->l=build(k+1,l,mid-1); ret->r=build(k+1,mid+1,r); ret->up(); return ret; } inline bool isbad(node*o){ return size(o->l)>alpha*o->s||size(o->r)>alpha*o->s; } void flatten(node *u,typename std::vector<node*>::iterator &it){ if(!u)return; flatten(u->l,it); *it=u; flatten(u->r,++it); } bool insert(node*&u,int k,const point &x,int dep){ if(!u){ u=new node(x); return dep<=0; } ++u->s; if(insert(x.d[k]<u->pid.d[k]?u->l:u->r,(k+1)%kd,x,dep-1)){ if(!isbad(u))return 1; if((int)A.size()<u->s)A.resize(u->s); typename std::vector<node*>::iterator it=A.begin(); flatten(u,it); u=build(k,0,u->s-1); } return 0; } inline int heuristic(const int h[])const{ int ret=0; for(size_t i=0;i<kd;++i)ret+=h[i]; return ret; } void nearest(node *u,int k,const point &x,T *h,T &mndist){ if(u==0||heuristic(h)>=mndist)return; point now=u->pid; int dist=u->pid.dist(x),old=h[k]; /*mndist=std::min(mndist,dist);*/ if(dist<mndist){ pQ.push(std::make_pair(dist,u->pid)); if((int)pQ.size()==qM+1){ mndist=pQ.top().first,pQ.pop(); } } if(x.d[k]<u->pid.d[k]){ nearest(u->l,(k+1)%kd,x,h,mndist); h[k]=abs(x.d[k]-u->pid.d[k]); nearest(u->r,(k+1)%kd,x,h,mndist); }else{ nearest(u->r,(k+1)%kd,x,h,mndist); h[k]=abs(x.d[k]-u->pid.d[k]); nearest(u->l,(k+1)%kd,x,h,mndist); } h[k]=old; } std::vector<point>in_range; void range(node *u,int k,const point&mi,const point&ma){ if(!u)return; bool is=1; for(int i=0;i<kd;++i) if(u->pid.d[i]<mi.d[i]||ma.d[i]<u->pid.d[i]){ is=0;break; } if(is)in_range.push_back(u->pid); if(mi.d[k]<=u->pid.d[k])range(u->l,(k+1)%kd,mi,ma); if(mi.d[k]>=u->pid.d[k])range(u->r,(k+1)%kd,mi,ma); } public: kd_tree(const T &INF,double a=0.75):alpha(a),loga(log2(1.0/a)),INF(INF){} inline void clear(){ clear(root),root=0; } inline void build(int n,const point *p){ clear(root),A.resize(n); for(int i=0;i<n;++i)A[i]=new node(p[i]); root=build(0,0,n-1); } inline void insert(const point &x){ insert(root,0,x,std::__lg(size(root))/loga); } inline T nearest(const point &x,int k){ qM=k; T mndist=INF,h[kd]={}; nearest(root,0,x,h,mndist); mndist=pQ.top().first; pQ=std::priority_queue<std::pair<T,point > >(); return mndist;/*回傳離x第k近的點的距離*/ } inline const std::vector<point> &range(const point&mi,const point&ma){ in_range.clear(); range(root,0,mi,ma); return in_range;/*回傳介於mi到ma之間的點vector*/ } inline int size(){return root?root->s:0;} }; #endif kd_tree<int,2> kdt(INT_MAX); int t,n,a; kd_tree<int,2>::point x; int main(){ scanf("%d",&t); while(t--){ kdt.clear(); scanf("%d",&n); while(n--){ scanf("%d%d%d",&a,&x.d[0],&x.d[1]); if(a)printf("%d\n",kdt.nearest(x,1)); else kdt.insert(x); } } return 0; } |
第二種做法code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | #include<stdio.h> #include<limits.h> #include<assert.h> //using namespace std; #ifndef SUNMOON_DYNEMIC_KD_TREE #define SUNMOON_DYNEMIC_KD_TREE #include<algorithm> #include<vector> template<typename T,size_t kd> class kd_tree{ public: struct point{ T d[kd]; inline T dist(const point &x)const{ T ret=0; for(size_t i=0;i<kd;++i)ret+=std::abs(d[i]-x.d[i]); return ret; } inline bool operator<(const point &b)const{ return d[0]<b.d[0]; } }; private: struct node{ node *l,*r; point pid; node(const point &p):l(0),r(0),pid(p){} }*root; const T INF; std::vector<node*> A; int s; struct __cmp{ int sort_id; inline bool operator()(const node*x,const node*y)const{ return x->pid.d[sort_id]<y->pid.d[sort_id]; } }cmp; void clear(node *o){ if(!o)return; clear(o->l); clear(o->r); delete o; } node* build(int k,int l,int r){ if(l>r)return 0; if(k==kd)k=0; int mid=(l+r)/2; cmp.sort_id=k; std::nth_element(A.begin()+l,A.begin()+mid,A.begin()+r+1,cmp); node *ret=A[mid]; ret->l=build(k+1,l,mid-1); ret->r=build(k+1,mid+1,r); return ret; } inline int heuristic(const int h[])const{ int ret=0; for(size_t i=0;i<kd;++i)ret+=h[i]; return ret; } node **mnp; int mnk; void findmin(node*&o,int d,int k){ if(!o)return; if(!mnp||o->pid.d[d]<(*mnp)->pid.d[d]){ mnp=&o; mnk=k; } findmin(o->l,d,(k+1)%kd); if(d==k)return; findmin(o->r,d,(k+1)%kd); } void nearest_for_erase(node *&u,int k,const point &x,T *h,T &mndist){ if(u==0||heuristic(h)>=mndist)return; point now=u->pid; int dist=u->pid.dist(x),old=h[k]; if(dist<mndist){ mnp=&u; mnk=k; if(!(mndist=dist))return; } if(x.d[k]<u->pid.d[k]){ nearest_for_erase(u->l,(k+1)%kd,x,h,mndist); h[k]=abs(x.d[k]-u->pid.d[k]); nearest_for_erase(u->r,(k+1)%kd,x,h,mndist); }else{ nearest_for_erase(u->r,(k+1)%kd,x,h,mndist); h[k]=abs(x.d[k]-u->pid.d[k]); nearest_for_erase(u->l,(k+1)%kd,x,h,mndist); } h[k]=old; } public: kd_tree(const T &INF):INF(INF),s(0){} inline void clear(){ clear(root),root=0; } inline void build(int n,const point *p){ clear(root),A.resize(s=n); for(int i=0;i<n;++i)A[i]=new node(p[i]); root=build(0,0,n-1); } inline bool erase(point p){ T mndist=1,h[kd]={}; nearest_for_erase(root,0,p,h,mndist); if(mndist)return 0; for(node **o=mnp;;){ if((*o)->r); else if((*o)->l){ (*o)->r=(*o)->l; (*o)->l=0; }else{ delete *o; (*o)=0; --s; return 1; } mnp=0; findmin((*o)->r,mnk,(mnk+1)%kd); (*o)->pid=(*mnp)->pid; o=mnp; } } inline T nearest(const point &x){ T mndist=INF,h[kd]={}; nearest_for_erase(root,0,x,h,mndist); return mndist;/*回傳離x最近的點的距離*/ } inline int size(){return s;} }; #endif kd_tree<int,2> kdt(INT_MAX); int t,n; kd_tree<int,2>::point x[200005],in[200005]; int ans[200005],a[200005],top; int main(){ scanf("%d",&t); while(t--){ kdt.clear(); scanf("%d",&n); top=0; for(int i=0;i<n;++i){ scanf("%d%d%d",&a[i],&x[i].d[0],&x[i].d[1]); if(!a[i])in[top++]=x[i]; } kdt.build(top,in); top=0; while(n--){ if(a[n])ans[top++]=kdt.nearest(x[n]); else assert(kdt.erase(x[n])); } while(top--)printf("%d\n",ans[top]); } return 0; } |
沒有留言:
張貼留言