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]));
}