bzoj2648 SJY摆棋子

本文主要是介绍bzoj2648 SJY摆棋子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是
曼哈顿距离 即(|x1-x2|+|y1-y2|)
。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。 Input 第一行两个数 N M 以后M行，每行3个数 t x y 如果t=1 那么放下一个黑色棋子 如果t=2 那么放下一个白色棋子
Output 对于每个T=2 输出一个最小距离

kdtree，插入直接暴力。经试验替罪羊的效率不高。
UPD：是我写替罪羊的姿势不对。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define R(k) for (int k=0;k<2;k++)
const int oo=0x3f3f3f3f,lim=100000;
int D,n,m,ans,root,lson[1000010],rson[1000010],mn[1000010][2],mx[1000010][2],tot;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
struct point
{int x[2];bool operator < (const point &pp) const{return x[D]<pp.x[D];}
}a[1000010],tem;
void up(int u,int v)
{if (!v) return;R(k){mn[u][k]=min(mn[u][k],mn[v][k]);mx[u][k]=max(mx[u][k],mx[v][k]);}
}
int build(int l,int r,int d)
{if (l>r) return 0;D=d;int mid=(l+r)/2;nth_element(a+l,a+mid,a+r+1);R(k) mn[mid][k]=mx[mid][k]=a[mid].x[k];up(mid,lson[mid]=build(l,mid-1,d^1));up(mid,rson[mid]=build(mid+1,r,d^1));return mid;
}
void ins(int u,int d)
{D=d;if (tem<a[u]){if (lson[u]) ins(lson[u],d^1);else{lson[u]=++tot;a[tot]=tem;R(k) mn[tot][k]=mx[tot][k]=tem.x[k];lson[tot]=rson[tot]=0;}up(u,lson[u]);}else{if (rson[u]) ins(rson[u],d^1);else{rson[u]=++tot;a[tot]=tem;R(k) mn[tot][k]=mx[tot][k]=tem.x[k];lson[tot]=rson[tot]=0;}up(u,rson[u]);}
}
int dis(int u)
{if (!u) return oo;int ret=0;R(k) ret+=abs(a[u].x[k]-tem.x[k]);return ret;
}
int mndis(int u)
{if (!u) return oo;int ret=0;R(k){if (tem.x[k]<mn[u][k]) ret+=mn[u][k]-tem.x[k];if (tem.x[k]>mx[u][k]) ret+=tem.x[k]-mx[u][k];}return ret;
}
void qry(int u)
{int mnl,mnr;ans=min(ans,dis(u));mnl=mndis(lson[u]);mnr=mndis(rson[u]);if (mnl<mnr){if (mnl<ans) qry(lson[u]);if (mnr<ans) qry(rson[u]);}else{if (mnr<ans) qry(rson[u]);if (mnl<ans) qry(lson[u]);}
}
int main()
{int i,opt,clo=0;n=rd();m=rd();for (i=1;i<=n;i++)R(k) a[i].x[k]=rd();root=build(1,n,0);tot=n;while (m--){opt=rd();R(k) tem.x[k]=rd();if (opt==1){ins(root,0);/*if (++clo>lim){root=build(1,tot,0);clo=0;}*/}else{ans=oo;qry(root);printf("%d\n",ans);}}
}

这篇关于bzoj2648 SJY摆棋子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---