K-D Tree在信息学竞赛中的应用
n+e
posted @ 2015年7月22日 07:55
in Interesting
with tags
kd-tree
, 5738 阅读
K-D Tree在信息学竞赛中的应用
福州一中 n+e
0. Update in 20160731:施工完毕
---------------------------------------->>>戳这里
1. 简介
Q:kdtree是啥我怎么没听说过?
A:kdtree不仅是一个大模板,还是通用的骗分神器呢
Q:我要学找哪里学?
A:看下面的讲解吧...
2. 基本用法
2.1. 节点
2.2. 估价
2.3. 构树
2.4. 查询
2.5. k近点的实现
3. 从我的一道原创题说起
3.1. Bzoj-4066 简单题(kdtree的重构)
3.2. Bzoj-4154 [Ipsc2015]Generating Synergy(kdtree替代树套树)
3.3. Bzoj-3489 A Simple Rmq Problem(kdtree替代可持久化树套树)
3.4. Ctsc2015 Shallot || Uoj Round 8 决战圆锥曲线(kdtree替代重量平衡树套线段树维护凸包)
3.5. Xj Noi2015训练19 不可视境界线(kdtree优化dp)
3.5.1. 题目大意
给定N,A[],B[],分析题目以后会得到如下的Dp方程:$$f_i=\min(\sqrt{f_j^2+(A_i-A_j)^2})(0\le j\lt i,\ A_i\ge B_j)$$
$N\le 10^5,\ 1\le A_i\le 10^6,\ 0\le B_i\le 10^6$
3.5.2 好像直接kdtree优化一下Dp就好了并不需要套什么数据结构啊...我错了我会补的
#include<cstdio> #include<cmath> #include<algorithm> #define N 100010 #define T 1<<18 int n,x[N],b[N],dx[N];long long f[N]; #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) #define sqr(x) (1LL*(x)*(x)) #define mt(o) x0[o]=min(x0[o<<1],x0[o<<1|1]),x1[o]=max(x1[o<<1],x1[o<<1|1]),y0[o]=min(y0[o<<1],y0[o<<1|1]),vis[o]=vis[o<<1]|vis[o<<1|1] class KDTree{public: long long ans,tmp,sf,y0[T]; int pos,lim,x,vis[T],x0[T],x1[T],id[N],L[T],R[T],i; void bt(int o,int l,int r){ if(l==r){ L[o]=R[o]=dx[l]; if(l==0)vis[o]=1,y0[o]=x0[o]=x1[o]=0; else y0[o]=1LL<<60,x0[o]=1<<20; }else{ int mid=l+r>>1; bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);mt(o); L[o]=L[o<<1],R[o]=R[o<<1|1]; } } void _ins(int o,int l,int r){ if(l==r)y0[o]=sf,x0[o]=x1[o]=pos,vis[o]=1,id[l]=i; else{ int mid=l+r>>1; if(pos<=R[o<<1])_ins(o<<1,l,mid); else _ins(o<<1|1,mid+1,r);mt(o); } } void ins(int idt,int xi,long long fi){ i=idt,pos=xi,sf=fi,_ins(1,0,n); } #define dis(o) y0[o]+sqr(max(max(x-x1[o],x0[o]-x),0)) void _query(int o,int l,int r){ if(!vis[o]||dis(o)>=ans)return; if(l==r){ if(tmp=y0[o]+sqr(x0[o]-x),tmp<ans)ans=tmp,pos=id[l];return; } int mid=l+r>>1,d0=dis(o<<1),d1=dis(o<<1|1); if(d1<=d0){ _query(o<<1|1,mid+1,r); if(lim<=R[o<<1])_query(o<<1,l,mid); }else{ if(lim<=R[o<<1])_query(o<<1,l,mid); _query(o<<1|1,mid+1,r); } } int query(int x0,int l){ return pos=-1,ans=1LL<<60,lim=l,x=x0,_query(1,0,n),pos; } }kdt; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",x+i,b+i),dx[i]=x[i]; std::sort(dx,dx+1+n); kdt.bt(1,0,n); for(int i=1,j;i<=n;i++) if(j=kdt.query(x[i],b[i]),j!=-1) kdt.ins(i,x[i],f[i]=f[j]+sqr(x[i]-x[j])); printf("%.4lf\n",sqrt(f[n])); }