首页 > 代码库 > 【BZOJ2626】JZPFAR kd-tree+堆

【BZOJ2626】JZPFAR kd-tree+堆

2024-10-27 10:41:01   208人阅读

【BZOJ2626】JZPFAR

Description

　　平面上有n个点。现在有m次询问，每次给定一个点(px, py)和一个整数k，输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同，那么认为标号较小的点距离较大。

Input

　　第一行，一个整数n，表示点的个数。
　　下面n行，每行两个整数x_i, y_i，表示n个点的坐标。点的标号按照输入顺序，分别为1..n。
　　下面一行，一个整数m，表示询问个数。
　　下面m行，每行三个整数px_i, py_i, k_i，表示一个询问。

Output

　　m行，每行一个整数，表示相应的询问的答案。

Sample Input

3
0 0
0 1
0 2
3
1 1 2
0 0 3
0 1 1

Sample Output

3
1
1

数据规模和约定
　　50%的数据中，n个点的坐标在某范围内随机分布。
　　100%的数据中，n<=10^5, m<=10^4, 1<=k<=20，所有点(包括询问的点)的坐标满足绝对值<=10^9，n个点中任意两点坐标不同，m个询问的点的坐标在某范围内随机分布。

题解：kd-tree+一个最小堆。

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <queue>#include <utility>#define x2(_) ((_)*(_))#define rep for(int i=0;i<=1;i++)#define MP(A,B)	make_pair(A,B)using namespace std;typedef long long ll;typedef pair<ll,int> pli;const int maxn=100010;struct kd{	ll v[2],sm[2],sn[2];	int ls,rs,org,om;	kd () {}	kd (ll a,ll b,int c)	{v[0]=sm[0]=sn[0]=a,v[1]=sm[1]=sn[1]=b,ls=rs=0,org=om=c;}	ll& operator [] (int a) {return v[a];}}t[maxn];int n,m,D,A,B,root;priority_queue<pli> pq;int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}bool cmp(kd a,kd b){	return (a[D]==b[D])?(a[D^1]<b[D^1]):(a[D]<b[D]);}void pushup(int x,int y){	rep	t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);	t[x].om=min(t[x].om,t[y].om);}int build(int l,int r,int d){	if(l>r)	return 0;	int mid=l+r>>1;	D=d,nth_element(t+l,t+mid,t+r+1,cmp);	t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);	if(t[mid].ls)	pushup(mid,t[mid].ls);	if(t[mid].rs)	pushup(mid,t[mid].rs);	return mid;}pli getdis(int x){	return MP(-max(x2(t[x].sm[0]-A),x2(t[x].sn[0]-A))-max(x2(t[x].sm[1]-B),x2(t[x].sn[1]-B)),t[x].om);}void query(int x){	if(!x||getdis(x)>pq.top())	return ;	pli tmp=MP(-x2(t[x][0]-A)-x2(t[x][1]-B),t[x].org);	if(tmp<pq.top())		pq.push(tmp),pq.pop();	if(getdis(t[x].ls)<getdis(t[x].rs))	query(t[x].ls),query(t[x].rs);	else	query(t[x].rs),query(t[x].ls);}int main(){	n=rd();	int i,j,a,b,c;	for(i=1;i<=n;i++)	a=rd(),b=rd(),t[i]=kd(a,b,i);	root=build(1,n,0);	m=rd();	for(i=1;i<=m;i++)	{		A=rd(),B=rd(),c=rd();		while(!pq.empty())	pq.pop();		for(j=1;j<=c;j++)	pq.push(MP(1ll<<60,-1<<30));		query(root);		printf("%d\n",pq.top().second);	}	return 0;}//3 0 0 0 1 0 2 3 1 1 2 0 0 3 0 1 1

【BZOJ2626】JZPFAR kd-tree+堆


联系
我们