http://www.lydsy.com/JudgeOnline/problem.php?id=2648 (题目链接)
题意
动态维护二维平面上的点的插入以及最邻近域搜索。
Solution
KDtree板子，代码膜的XlightGod。复杂度真的萎，感觉主要还是剪枝。
理论：http://blog.csdn.net/silangquan/article/details/41483689
实现：http://blog.xlightgod.com/%E3%80%90bzoj2648%E3%80%91sjy%E6%91%86%E6%A3%8B%E5%AD%90/
细节
码农数据结构题
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=1000010;
int n,rt,K,m,ans; struct node {
int v[2],mn[2],mx[2],son[2];
friend bool operator < (const node &a,const node &b) {return a.v[K]<b.v[K];}
int& operator [] (int x) {return son[x];}
}tr[maxn],S; void pushup(int k) {
for (int i=0;i<2;i++) {
if (!tr[k][i]) continue;
for (int j=0;j<2;j++) {
tr[k].mx[j]=max(tr[k].mx[j],tr[tr[k][i]].mx[j]);
tr[k].mn[j]=min(tr[k].mn[j],tr[tr[k][i]].mn[j]);
}
}
}
int build(int l,int r,int p) {
K=p;int mid=(l+r)>>1;
nth_element(tr+l,tr+mid,tr+r+1); //闭,闭,开
for (int i=0;i<2;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].v[i];
if (l<mid) tr[mid][0]=build(l,mid-1,p^1);
if (r>mid) tr[mid][1]=build(mid+1,r,p^1);
pushup(mid);
return mid;
}
void insert(int &k,int p) {
K=p;
if (!k) {
k=++n;tr[k]=S;
for (int i=0;i<2;i++) tr[k].mx[i]=tr[k].mn[i]=tr[k].v[i];
return;
}
else insert(tr[k][S<tr[k]],p^1);
pushup(k);
}
int dis(node a,node b) {
int res=0;
for (int i=0;i<2;i++) res+=abs(a.v[i]-b.v[i]);
return res;
}
int eva(int k) { //类似估价函数
if (!k) return inf;
int res=0;
for (int i=0;i<2;i++) res+=max(0,tr[k].mn[i]-S.v[i])+max(0,S.v[i]-tr[k].mx[i]);
return res;
}
void query(int k) {
ans=min(ans,dis(S,tr[k]));
int dl=eva(tr[k][0]),dr=eva(tr[k][1]);
if (dl<dr) {
if (dl<ans) query(tr[k][0]);
if (dr<ans) query(tr[k][1]);
}
else {
if (dr<ans) query(tr[k][1]);
if (dl<ans) query(tr[k][0]);
}
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d%d",&tr[i].v[0],&tr[i].v[1]);
rt=build(1,n,0);
for (int op,i=1;i<=m;i++) {
scanf("%d%d%d",&op,&S.v[0],&S.v[1]);
if (op==1) insert(rt,0);
else {
ans=inf;
query(rt);
printf("%d\n",ans);
}
}
return 0;
}
Solution
CDQ分治。考虑在查询点左下方的点里面$|x+y|$最大的，这个每次CDQ分治的时候按照x排序然后树状数组维护一下就可以了。然后我们将坐标轴旋转一下，做4个方向，然后就搞完了。
TTTTTLE，过不了了，也许你需要底层优化。
细节
清空的时候注意复杂度。
代码
// bzoj2648
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483600
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
inline int gi() {
int x=0,f=1;char ch=getchar();
while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=1000010;
int n,m,X,Y,c[maxn];
struct data {int x,y,id,op,ans;}q[maxn],nq[maxn]; bool cmp(data a,data b) {return a.x<b.x;}
bool cmpid(data a,data b) {return a.id<b.id;}
int lowbit(int x) {
return x&-x;
}
void modify(int x,int val) {
for (int i=x;i<=Y;i+=lowbit(i)) c[i]=max(c[i],val);
}
void clear(int x) {
for (int i=x;i<=Y;i+=lowbit(i)) c[i]=-inf;
}
int query(int x) {
int res=-inf;
for (int i=x;i;i-=lowbit(i)) res=max(res,c[i]);
return res;
}
void solve(int l,int r) {
if (l==r) return;
int mid=(l+r)>>1,l1=l,l2=mid+1;
for (int i=l;i<=r;i++) q[i].id<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i];
for (int i=l;i<=r;i++) q[i]=nq[i];
for (int i=l,j=mid+1;i<=mid || j<=r;) {
if (j>r || (i<=mid && q[i].x<=q[j].x)) {
if (q[i].op==1) modify(q[i].y,q[i].x+q[i].y);
i++;
}
else {
if (q[j].op==2) q[j].ans=min(q[j].ans,abs(q[j].x+q[j].y-query(q[j].y)));
j++;
}
}
for (int i=l;i<=mid;i++) if (q[i].op==1) clear(q[i].y);
solve(l,mid);solve(mid+1,r);
}
int main() {
scanf("%d%d",&n,&m);X=-inf,Y=-inf;
for (int i=1;i<=n;i++) {
q[i].x=gi()+1,q[i].y=gi()+1;
X=max(q[i].x,X);Y=max(q[i].y,Y);
q[i].id=i,q[i].op=1;q[i].ans=inf;
}
for (int i=1;i<=m;i++) {
q[i+n].op=gi(),q[i+n].x=gi()+1,q[i+n].y=gi()+1;
X=max(q[i+n].x,X);Y=max(q[i+n].y,Y);
q[i+n].id=i+n;q[i+n].ans=inf;
}
n+=m;
for (int i=1;i<=n;i++) c[i]=-inf;
sort(q+1,q+1+n,cmp);solve(1,n);
for (int i=1;i<=n;i++) q[i].x=X-q[i].x+1;
sort(q+1,q+1+n,cmp);solve(1,n);
for (int i=1;i<=n;i++) q[i].y=Y-q[i].y+1;
sort(q+1,q+1+n,cmp);solve(1,n);
for (int i=1;i<=n;i++) q[i].x=X-q[i].x+1;
sort(q+1,q+1+n,cmp);solve(1,n);
for (int i=1;i<=n;i++) if (q[i].ans!=inf) printf("%d\n",q[i].ans);
return 0;
}