【bzoj2648】$SJY$摆棋子
题目大意
在一个很大的棋盘上，摆好了$n$个黑色棋子，现在执行$m$次操作，分为两种：
摆一个黑色棋子
摆一个白色棋子，同时输出距离这个棋子最近的一个黑色棋子与它的距离(曼哈顿距离)
值得注意的是，一个地方可以放两个棋子
数据范围
$n,m\leqslant 500000$
题解
对于这一个问题，有一个简单思路，每次新摆一个白色棋子然后枚举黑色棋子，计算曼哈顿距离
很好，但是$n$，$m$到了五十万[捂脸]
这时候我们引入一个东西，叫做$K-D\ Tree$
Tree？这是二维的图哦嗯，实际上这是引入$K-D\ Tree$，而不是别的什么玄学结构的原因之一
这个$Tree$是这样建树的：
选定一个维度
针对每个点在这个维度上的参数$a_1,a_2,a_3..a_n$，用$STL$中的$nth\_element()$排序，使得在中间值左边的值全都比它小，右边的值全都比它大，但不保证有序
把中间值取出，把这个点当成根节点
选定另一个维度，递归左边的值(左平面)作为左子树，再递归右边的值(右平面)作为右子树
递归完之后更新根节点记录的信息
当然如果只有一个维度，它的效率比别的数据结构较之一般，但是在多维度上，就显示出很强势的一面啦
对于这道题，插入和查询怎么办？插入一个新的节点，只要针对某一维度上的参数与节点作比较，然后递归到子树即可
查询就需要节点记录的信息了
例如这道题，节点记录平面上极值点的坐标参数，然后比较对于查询位置来说哪个平面上的极值点更近，就递归哪个平面(子树)
关于其他的东西，我在代码旁做了比较详细的注释，那么这道题的题解就结束了！
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7ffffff
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,root,D;
struct data{
int c[2],mn[2],mx[2],l,r;
data(int x=0,int y=0){l=r=0,c[0]=x,c[1]=y;}
}p[500500];
bool operator<(data a,data b){return a.c[D]<b.c[D];}
inline int dis(data a,data b){return abs(a.c[0]-b.c[0])+abs(a.c[1]-b.c[1]);}
struct kdtree{
int ans;
data t[1000500],T;
void pushup(int k){ //更新平面内两个维度的参数极大极小值
data l=t[t[k].l],r=t[t[k].r];
For(i,0,1){
if (t[k].l) t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]);
if (t[k].r) t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]);
}
}
int build(int l,int r,int dim){ //dim是每次建树的维度
D=dim; //确认排序时的关键值(当前维度上的参数)
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1); //比较参数，排序使得中间值左边的参数比它小，右边的参数比它大(不保证左右有序)
t[mid]=p[mid];
For(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].c[i];
if (l<mid) t[mid].l=build(l,mid-1,dim^1); //分成两个平面，更换维度递归（图是二维）
if (r>mid) t[mid].r=build(mid+1,r,dim^1);
pushup(mid); //回溯更新
return mid;
}
void insert(data p){
T=p;
insert(root,0);
}
void insert(int k,int dim){
if (T.c[dim]>=t[k].c[dim]){ //比较当前维度上根节点的参数与新节点的参数
if (t[k].r) insert(t[k].r,dim^1); //递归右子树
else{
t[k].r=++n,t[n]=T; //插入新节点
For(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].c[i];
}
}
else{
if (t[k].l) insert(t[k].l,dim^1); //递归左子树
else{
t[k].l=++n,t[n]=T; //插入新节点
For(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].c[i];
}
}
pushup(k); //回溯更新
}
int get(data p){
int sum=0;
For(i,0,1) sum+=max(p.mn[i]-T.c[i],0)+max(T.c[i]-p.mx[i],0);
return sum;
}
int query(data p){
ans=inf,T=p;
query(root);
return ans;
}
void query(int k){
int d,dl=inf,dr=inf;
d=dis(t[k],T); //中间值到询问位置的距离
ans=min(ans,d);
if (t[k].l) dl=get(t[t[k].l]); //记录询问位置离左平面上的点的最短距离
if (t[k].r) dr=get(t[t[k].r]); //记录询问位置离右平面上的点的最短距离
if (dl<dr){
if (dl<ans) query(t[k].l);
if (dr<ans) query(t[k].r);
}
//如果dl<dr，可能先递归左平面更新后得到ans<dr，也就是已经确定更优，那么不需要再递归右平面，以下同理
else{
if (dr<ans) query(t[k].r);
if (dl<ans) query(t[k].l);
}
}
}kd;
int main(){
n=read(),m=read();
For(i,1,n) p[i].c[0]=read(),p[i].c[1]=read();
root=kd.build(1,n,0);
while (m--){
int flag=read(),x=read(),y=read();
if (flag==1) kd.insert(data(x,y));
else printf("%d\n",kd.query(data(x,y)));
}
return 0;
}安利一下：
【bzoj1941】$Hide\ and\ Seek$
题目大意
给定$n$个点的坐标$(x,y)$，在其中选定一个点$A$
使得$A$到最远点的距离减去到最近点的距离最小，然后输出这个最小值
注意两点，此题的距离指的是曼哈顿距离
且$A$到最近点的距离不能为零，即最近点不能是其本身
数据范围
$n\leqslant 500000,0\leqslant x,y\leqslant 10^8$，保证数据没有重点保证$n\leqslant 2$
题解
在上一题，在询问中我们需要求到最近点的距离
这一题其实也差不多，只是要在询问中再求到最远点的距离，具体看代码
由于数据范围又是在五十万之内，是不是很熟悉？
所以我是暴力枚举每个点，如果有更优值就更新答案
或许有更好的玄学（划掉）想法呢？
程序
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7ffffff
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,root,ans,D;
int x[500500],y[500500];
struct data{
int c[2],mn[2],mx[2],l,r;
data(int x=0,int y=0){l=r=0,c[0]=x,c[1]=y;}
}p[500500];
bool operator<(data a,data b){return a.c[D]<b.c[D];}
inline int dis(data a,data b){return abs(a.c[0]-b.c[0])+abs(a.c[1]-b.c[1]);}
struct kdtree{
int mx,mn;
data t[1000500],T;
void pushup(int k){
data l=t[t[k].l],r=t[t[k].r];
For(i,0,1){
if (t[k].l) t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]);
if (t[k].r) t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]);
}
}
int build(int l,int r,int dim){
D=dim;
int mid=(l+r)>>1;
nth_element(p+l,p+mid,p+r+1);
t[mid]=p[mid];
For(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].c[i];
if (l<mid) t[mid].l=build(l,mid-1,dim^1);
if (r>mid) t[mid].r=build(mid+1,r,dim^1);
pushup(mid);
return mid;
}
int query(data p){
T=p;
mx=-inf;querymx(root);
mn=inf;querymn(root);
return mx-mn;
}
int getmn(data p){
int sum=0;
For(i,0,1) sum+=max(T.c[i]-p.mx[i],0)+max(p.mn[i]-T.c[i],0);
return sum;
}
int getmx(data p){
int sum=0;
For(i,0,1) sum+=max(abs(T.c[i]-p.mx[i]),abs(p.mn[i]-T.c[i]));
return sum;
}
void querymn(int k){
int d=dis(t[k],T),dl=inf,dr=inf;
if (d) mn=min(mn,d);
if (t[k].l) dl=getmn(t[t[k].l]);
if (t[k].r) dr=getmn(t[t[k].r]);
if (dl<dr){
if (dl<mn) querymn(t[k].l);
if (dr<mn) querymn(t[k].r);
}
else{
if (dr<mn) querymn(t[k].r);
if (dl<mn) querymn(t[k].l);
}
}
void querymx(int k){
int dl=-inf,dr=-inf;
mx=max(mx,dis(t[k],T));
if (t[k].l) dl=getmx(t[t[k].l]);
if (t[k].r) dr=getmx(t[t[k].r]);
if (dl>dr){
if (dl>mx) querymx(t[k].l);
if (dr>mx) querymx(t[k].r);
}
else{
if (dr>mx) querymx(t[k].r);
if (dl>mx) querymx(t[k].l);
}
}
}kd;
int main(){
n=read();
For(i,1,n){
x[i]=read(),y[i]=read();
p[i].c[0]=x[i],p[i].c[1]=y[i];
}
root=kd.build(1,n,0);
ans=inf;
For(i,1,n) ans=min(ans,kd.query(data(x[i],y[i])));
printf("%d\n",ans);
return 0;
}
鄂公网安备 42010202000505 号