題目大意
有N個(gè)賓館，坐落在二維直角坐標(biāo)平面上，每個(gè)賓館都有一個(gè)價(jià)格。
有M個(gè)人，要去找一個(gè)離他最近的賓館住宿（歐幾里得距離），并且要求價(jià)格不超過一個(gè)值。
n<=2×105，m<=2×104
解答
先按照價(jià)格離線，然后用kd-tree維護(hù)。我的做法是先把N個(gè)賓館的kd-tree先靜態(tài)處理出來，然后再根據(jù)價(jià)格一個(gè)一個(gè)添加和查詢。
kd-tree的構(gòu)樹時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度和線段樹一樣，單個(gè)添加操作的時(shí)間復(fù)雜度是O(logn)，單個(gè)詢問的時(shí)間復(fù)雜度是O(n^(1-1/k)) (k是維度)，這題的詢問時(shí)間復(fù)雜度是O(sqrt(n))。所以總時(shí)間復(fù)雜度是O(n×logn + m×sqrt(n))。
Q神的做法是替罪羊樹+kd-tree，番茄猜大概就是按照價(jià)格動(dòng)態(tài)構(gòu)造kd-tree，當(dāng)平衡度很差的時(shí)候仿照替罪羊數(shù)重新構(gòu)一下。
第一次寫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 // 讀入結(jié)構(gòu)體
{
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 // 構(gòu)造一個(gè)k維結(jié)構(gòu)體
{
int p[2];
kdpoint(int x=0,int y=0)
{
p[0]=x;
p[1]=y;
}
};
kdpoint T[maxn]; // 記錄酒店位置，用于靜態(tài)處理kd-tree
int N,M;
Typ A[maxn]; // 記錄讀入酒店信息，id此處記錄價(jià)格
int Ans[maxn]; // 記錄詢問答案
namespace kdtree
{
struct node
{
kdpoint p; // 劃分點(diǎn)
int keyd; // 第一關(guān)鍵字
int D[4]; // 狀態(tài)維度，0、2表示第一、第二維度下界，1、3表示第一、第二維度上界
int left,right; // 左右兒子
void init(kdpoint &pp,int d)
{
p=pp;
keyd=d;
D[0]=D[2]=maxn; // 因?yàn)橄阮A(yù)處理kd-tree，狀態(tài)維度初始為無
D[1]=D[3]=-1;
left=right=0;
}
void up(int &x,int &y) // 添加點(diǎn)后，更新維度狀態(tài)
{
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狀態(tài)
int id[maxn*4]; // id為-1表示這點(diǎn)尚未添加，否則已經(jīng)添加，等于酒店編號
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) // 計(jì)算點(diǎn)到某矩形的最近距離
{
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) // 初始化，靜態(tài)構(gòu)樹
{
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); // 一個(gè)求出中位數(shù)，并且把區(qū)間的數(shù)按照中位數(shù)劃分成兩邊的函數(shù)
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) // 根據(jù)已知最優(yōu)解，判斷能否更新答案
{
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;
}
