题目大意
有N个宾馆，坐落在二维直角坐标平面上，每个宾馆都有一个价格。
有M个人，要去找一个离他最近的宾馆住宿（欧几里得距离），并且要求价格不超过一个值。
n<=2×105，m<=2×104
解答
先按照价格离线，然后用kd-tree维护。我的做法是先把N个宾馆的kd-tree先静态处理出来，然后再根据价格一个一个添加和查询。
kd-tree的构树时间复杂度是O(nlogn)，空间复杂度和线段树一样，单个添加操作的时间复杂度是O(logn)，单个询问的时间复杂度是O(n^(1-1/k)) (k是维度)，这题的询问时间复杂度是O(sqrt(n))。所以总时间复杂度是O(n×logn + m×sqrt(n))。
Q神的做法是替罪羊树+kd-tree，番茄猜大概就是按照价格动态构造kd-tree，当平衡度很差的时候仿照替罪羊数重新构一下。
第一次写kd-tree，写的比较挫，以后多写写精简一下。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define rep(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))
//__builtin_popcountll
using std::sort;
using std::max;
using std::min;
using std::swap;
using std::vector;
const int buffer_length=1e7+10;
struct reader
{
char buf[buffer_length];
int len;
int cur;
void init()
{
len=fread(buf,buffer_length,1,stdin);
cur=0;
}
void read(int &x)
{
for (; buf[cur]<'0' || buf[cur]>'9'; cur++);
x=0;
for (; buf[cur]>='0' && buf[cur]<='9'; cur++)
x=x*10+buf[cur]-48;
}
}kdb;
const int maxn=200000+100;
struct Typ // 读入结构体
{
int x,y,id;
Typ(int a=0,int b=0,int c=0)
{
x=a,y=b,id=c;
}
};
vector <Typ> ope[maxn],Q[maxn];
struct kdpoint // 构造一个k维结构体
{
int p[2];
kdpoint(int x=0,int y=0)
{
p[0]=x;
p[1]=y;
}
};
kdpoint T[maxn]; // 记录酒店位置，用于静态处理kd-tree
int N,M;
Typ A[maxn]; // 记录读入酒店信息，id此处记录价格
int Ans[maxn]; // 记录询问答案
namespace kdtree
{
struct node
{
kdpoint p; // 划分点
int keyd; // 第一关键字
int D[4]; // 状态维度，0、2表示第一、第二维度下界，1、3表示第一、第二维度上界
int left,right; // 左右儿子
void init(kdpoint &pp,int d)
{
p=pp;
keyd=d;
D[0]=D[2]=maxn; // 因为先预处理kd-tree，状态维度初始为无
D[1]=D[3]=-1;
left=right=0;
}
void up(int &x,int &y) // 添加点后，更新维度状态
{
if (x<D[0]) D[0]=x;
if (x>D[1]) D[1]=x;
if (y<D[2]) D[2]=y;
if (y>D[3]) D[3]=y;
}
};
int cnt,root,cmpD;
node Tree[maxn*4]; // kd-tree状态
int id[maxn*4]; // id为-1表示这点尚未添加，否则已经添加，等于酒店编号
long long minf; // 查询的最近距离
int ansid; // 查询的最近酒店编号
void init()
{
cnt=0;
}
long long sqr(int x)
{
return (bll)x*x;
}
long long point_to_rec(int &x,int &y,node &r) // 计算点到某矩形的最近距离
{
if (r.D[0]<=x && x<=r.D[1] && r.D[2]<=y && y<=r.D[3]) return 0;
if (r.D[0]<=x && x<=r.D[1])
return min(sqr(y-r.D[2]),sqr(y-r.D[3]));
if (r.D[2]<=y && y<=r.D[3])
return min(sqr(x-r.D[0]),sqr(x-r.D[1]));
return min(sqr(x-r.D[0]),sqr(x-r.D[1]))+min(sqr(y-r.D[2]),sqr(y-r.D[3]));
}
bool cmp(kdpoint a,kdpoint b)
{
if (a.p[cmpD]!=b.p[cmpD]) return a.p[cmpD]<b.p[cmpD];
return a.p[cmpD^1]<b.p[cmpD^1];
}
int maketree(int le,int ri,kdpoint a[],int d) // 初始化，静态构树
{
int w=++cnt;
id[w]=-1;
if (le==ri)
{
Tree[w].init(a[le],d);
return w;
}
cmpD=d;
int mid=(le+ri)>>1;
std::nth_element(a+le,a+mid,a+ri+1,cmp); // 一个求出中位数，并且把区间的数按照中位数划分成两边的函数
Tree[w].init(a[mid],d);
if (le<mid) Tree[w].left=maketree(le,mid-1,a,d^1);
if (mid<ri) Tree[w].right=maketree(mid+1,ri,a,d^1);
return w;
}
void build(int N,kdpoint a[])
{
root=maketree(1,N,a,0);
}
void modify(int w,kdpoint &tt,int &pid) // 添加操作
{
Tree[w].up(tt.p[0],tt.p[1]);
if (tt.p[0]==Tree[w].p.p[0] && tt.p[1]==Tree[w].p.p[1])
{
id[w]=pid;
return ;
}
cmpD=Tree[w].keyd;
if (cmp(tt,Tree[w].p))
{
modify(Tree[w].left,tt,pid);
}
else
{
modify(Tree[w].right,tt,pid);
}
}
void add(Typ &tt) // 添加，对外接口
{
kdpoint x=kdpoint(tt.x,tt.y);
int rr=tt.id;
modify(root,x,rr);
}
long long get_dist(const kdpoint &a,const kdpoint &b) // 求欧式距离的平方
{
return sqr(a.p[0]-b.p[0])+sqr(a.p[1]-b.p[1]);
}
bool check_out(kdpoint &tt,int &w) // 根据已知最优解，判断能否更新答案
{
long long ss=point_to_rec(tt.p[0],tt.p[1],Tree[w]);
return ss>minf;
}
void que(int w,kdpoint &tt) // 询问操作
{
if (w==0 || Tree[w].D[0]==maxn) return ;
if (check_out(tt,w)) return ;
if (id[w]!=-1)
{
long long ss=get_dist(tt,Tree[w].p);
if ((ss<minf) || (ss==minf && id[w]<ansid))
minf=ss,ansid=id[w];
}
cmpD=Tree[w].keyd;
if (cmp(tt,Tree[w].p))
{
que(Tree[w].left,tt);
que(Tree[w].right,tt);
}
else
{
que(Tree[w].right,tt);
que(Tree[w].left,tt);
}
}
int query(Typ &tt) // 询问，对外接口
{
kdpoint x=kdpoint(tt.x,tt.y);
minf=sqr(200000)*2LL;
ansid=-1;
que(root,x);
return ansid;
}
}
void Done()
{
using kdtree::add;
using kdtree::query;
For(i,1,max(N,M))
{
For(j,0,ope[i].size()-1)
{
add(ope[i][j]);
}
For(j,0,Q[i].size()-1)
{
Ans[Q[i][j].id]=query(Q[i][j]);
}
}
For(i,1,M)
{
int w=Ans[i];
printf("%d %d %d\n",A[w].x,A[w].y,A[w].id);
}
}
int main(int argc, char* argv[])
{
kdb.init();
int zz;
kdb.read(zz);
For(teset,1,zz)
{
kdb.read(N);
kdb.read(M);
For(i,1,max(N,M)) ope[i].clear();
For(i,1,max(N,M)) Q[i].clear();
For(i,1,N)
{
int x,y,p;
kdb.read(x),kdb.read(y),kdb.read(p);
ope[p].push_back(Typ(x,y,i));
A[i]=Typ(x,y,p);
T[i].p[0]=x;
T[i].p[1]=y;
}
For(i,1,M)
{
int x,y,p;
kdb.read(x),kdb.read(y),kdb.read(p);
Q[p].push_back(Typ(x,y,i));
}
kdtree::init();
kdtree::build(N,T);
Done();
}
return 0;
}
网友评论