自动搬运

查看原文

来自洛谷，原作者为

	zhengrunzhe 为世界上所有的美好而战

搬运于2025-08-24 21:41:42，当前版本为作者最后更新于2019-08-31 15:57:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先观察公式

$$cmp(i,j) =| ai - aj + bj - bi | + | ai - aj |$$

看到两个绝对值，左边一个绝对值加右边一个绝对值，是不是很像曼哈顿距离？

由于动态加点，这时候我们选择强上K-D Tree

普通的平面最近曼哈顿点对的估价函数我们是这样写的

$$max(minx-x,0)+max(x-maxx,0)+max(miny-y,0)+max(y-maxy,0) $$

同理，我们也需要对cmp函数进行正确的估价

一开始我是这么想的：

绝对值不等式：

$$|x|+|y|>=|x-y|$$

令

$$x=ai-aj+bj-bi,y=ai-aj$$

代入得

$$cmp(i,j)=|ai-aj+bj-bi|+|ai-aj|=|x|+|y|>=|x-y|$$

即

$$cmp(i,j)>=|ai-aj+bj-bi-(ai-aj)|$$ $$cmp(i,j)>=|bj-bi|$$

然后估价函数可以这么写：

$$max(minb-b,0)+max(b-maxb,0)$$

然后提交一波

//50分代码 请勿模仿
#include<cstdio>
#include<algorithm>
using namespace std;
template<class type>inline const void read(type &in)
{
	in=0;char ch=getchar();bool fh=0;
	while (ch<48||ch>57)fh=ch=='-'?1:fh,ch=getchar();
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
	if (fh)in=-in;
}
const int K=2,N=1e5+10,M=1e5+10,INF=2147483647;
int n,m,f;
struct point
{
	int d[K];
	inline const bool operator<(const point &p)const
	{
		return d[f]<p.d[f];
	}
	inline const friend int cmp(const point &a,const point &b)
	{
		return abs(a.d[0]-b.d[0]+b.d[1]-a.d[1])+abs(a.d[0]-b.d[0]);
	}
}w[N+M];
template<int K>class KD_Tree
{
	static const double alpha=0.75;
	private:
		struct tree
		{
			int size;
			tree *son[2];
			point range,mx,mn;
			inline const void pushup()
			{
				size=son[0]->size+1+son[1]->size;
				for (int i=0;i<K;i++)
					mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])),
					mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i]));
			}
			inline const bool unbalanced()
			{
				return son[0]->size>size*alpha||son[1]->size>size*alpha;
			}
			inline const int evalue(const point &x)
			{
				return max(mn.d[1]-x.d[1],0)+max(x.d[1]-mx.d[1],0);
			}
		}memory_pool[N+M],*recycle[N+M],*null,*tail,*root;
		int top,rnk,mn;
		inline const void init()
		{
			tail=memory_pool;
			null=tail++;
			root=null->son[0]=null->son[1]=null;
			for (int i=0;i<K;i++)
				null->range.d[i]=0,
				null->mx.d[i]=-INF,
				null->mn.d[i]=INF;
			null->size=top=0;
		}
		inline tree *spawn(const point &x)
		{
			tree *p=top?recycle[--top]:tail++;
			p->size=1;
			p->mn=p->mx=p->range=x;
			p->son[0]=p->son[1]=null;
			return p;
		}
		inline const void travel(tree *p)
		{
			if (p==null)return;
			travel(p->son[0]);
			w[++rnk]=p->range;
			recycle[top++]=p;
			travel(p->son[1]);
		}
		inline tree *build(int l,int r,int d)
		{
			if (l>r)return null;
			int mid=l+r>>1;f=d;
			nth_element(w+l,w+mid,w+r+1);
			tree *p=spawn(w[mid]);
			if (l==r)return p;
			p->son[0]=build(l,mid-1,(d+1)%K);
			p->son[1]=build(mid+1,r,(d+1)%K);
			p->pushup();
			return p;
		}
		inline const void rebuild(tree *&p)
		{
			rnk=0;
			travel(p);
			p=build(1,rnk,0);
		}
		inline tree **add(tree *&p,const point &x,int d)
		{
			if (p==null)return p=spawn(x),&null;
			tree **bad=add(p->son[p->range.d[d]<x.d[d]],x,(d+1)%K);
			p->pushup();
			if (p->unbalanced())bad=&p;
			return bad;
		}
		inline const void query(tree *p,const point &x)
		{
			if (p==null)return;//printf("(%d,%d)\n",p->range.d[0],p->range.d[1]);
			mn=min(mn,cmp(p->range,x));
			int f[2]={INF,INF};
			if (p->son[0]!=null)f[0]=p->son[0]->evalue(x);
			if (p->son[1]!=null)f[1]=p->son[1]->evalue(x);//printf("%d %d %d\n",mn,f[0],f[1]);
			bool t=f[0]>=f[1];
			if (f[t]<mn)query(p->son[t],x);t^=1;
			if (f[t]<mn)query(p->son[t],x);
		}
	public:
		inline KD_Tree(){init();}
		inline const void insert(const point &x)
		{
			tree **bad=add(root,x,0);
			if (*bad!=null)rebuild(*bad);
		}
		inline const int query(const point &x)
		{
			mn=INF;
			query(root,x);
			return mn;
		}
		inline const void build()
		{
			root=build(1,n,0);
		}
};
KD_Tree<K>kdt;
int main()
{
	read(n);read(m);
	for (int i=1;i<=n;i++)for (int j=0;j<K;j++)read(w[i].d[j]);
	kdt.build();
	while (m--)
	{
		int opt;point c;
		read(opt);
		for (int i=0;i<K;i++)read(c.d[i]);
		if (opt==1)kdt.insert(c);
		else printf("%d\n",kdt.query(c));
	}
	return 0;
}

就愉快的tle拿50分了

原因在于：这个估价函数太low了，正确性有保证但是无法获得合理高效的时效

然后我们再看一眼式子

$$cmp(i,j) =| ai - aj + bj - bi | + | ai - aj |$$ $$cmp(i,j)=|(bj-ai)-(bi-ai)|+|ai-aj|$$

我*，这不就是裸的平面最近点对吗

把(b-a)当做第一维，a当做第二维,cmp(i,j)就是点i,j的曼哈顿距离

于是愉快地K-D Tree通过了此题

//100分代码
#include<cstdio>
#include<algorithm>
using std::abs;
using std::max;
using std::min;
using std::nth_element;
template<class type>inline const void read(type &in)
{
	in=0;char ch=getchar();bool f=0;
	while (ch<48||ch>57){if (ch=='-')f=1;ch=getchar();}
	while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar();
	if (f)in=-in;
}
const int K=2,N=1e5+10,M=1e5+10,INF=2147483647;
int n,m,f;
struct point
{
	int d[K];
	inline point(int x=0,int y=0){d[0]=x;d[1]=y;}
	inline const bool operator<( const point &p)const
	{
		return d[f]<p.d[f];
	}
	inline const friend int manhattan( const point &a, const point &b)
	{
		int dis=0;
		for (int i=0;i<K;i++)dis+=abs(a.d[i]-b.d[i]);
		return dis;
	}
}w[N+M];
template<int K>class KD_Tree
{
	static const double alpha=0.75;
	private:
		struct tree
		{
			int size;
			tree *son[2];
			point range,mx,mn;
			inline const void pushup()
			{
				size=son[0]->size+1+son[1]->size;
				for (int i=0;i<K;i++)
					mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])),
					mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i]));
			}
			inline const bool unbalanced()
			{
				return son[0]->size>size*alpha||son[1]->size>size*alpha;
			}
			inline const int evalue(const point &x)
			{
				int f=0;
				for (int i=0;i<K;i++)f+=max(mn.d[i]-x.d[i],0)+max(x.d[i]-mx.d[i],0);
				return f;
			}
		}memory_pool[N+M],*recycle[N+M],*null,*tail,*root;
		int top,rnk,flag,mn;
		inline const void init()
		{
			tail=memory_pool;
			null=tail++;
			root=null->son[0]=null->son[1]=null;
			for (int i=0;i<K;i++)null->mx.d[i]=-INF,null->mn.d[i]=INF;
		}
		inline tree *spawn(const point &x)
		{
			tree *p=top?recycle[--top]:tail++;
			p->size=1;
			p->mn=p->mx=p->range=x;
			p->son[0]=p->son[1]=null;
			return p;
		}
		inline const void travel(tree *p)
		{
			if (p==null)return;
			travel(p->son[0]);
			w[++rnk]=p->range;
			recycle[top++]=p;
			travel(p->son[1]);
		}
		inline tree *build(int l,int r,int d)
		{
			if (l>r)return null;
			int mid=l+r>>1;f=d;
			nth_element(w+l,w+mid,w+r+1);
			tree *p=spawn(w[mid]);
			if (l==r)return p;
			p->son[0]=build(l,mid-1,d^1);
			p->son[1]=build(mid+1,r,d^1);
			p->pushup();
			return p;
		}
		inline const void rebuild(tree *&p,int d)
		{
			rnk=0;
			travel(p);
			p=build(1,rnk,d);
		}
		inline tree **insert(tree *&p,const point &x,int d)
		{
			if (p==null)return p=spawn(x),&null;
			tree **bad=insert(p->son[p->range.d[d]<x.d[d]],x,d^1);
			p->pushup();
			if (p->unbalanced())bad=&p,flag=d;
			return bad;
		}
		inline const void query(tree *p,const point &x)
		{
			mn=min(mn,manhattan(p->range,x));
			int f[2]={INF,INF};
			if (p->son[0]!=null)f[0]=p->son[0]->evalue(x);
			if (p->son[1]!=null)f[1]=p->son[1]->evalue(x);
			bool t=f[0]>=f[1];
			if (f[t]<mn)query(p->son[t],x);t^=1;
			if (f[t]<mn)query(p->son[t],x);
		}
	public:
		inline KD_Tree(){init();}
		inline const void insert(int x,int y)
		{
			tree **bad=insert(root,point(y-x,x),flag=0);
			if (*bad==null)return;
			rebuild(*bad,flag);
		}
		inline const int query(int x,int y)
		{
			mn=INF;
			query(root,point(y-x,x));
			return mn;
		}
};
KD_Tree<K>kdt;
int main()
{
	read(n);read(m);
	for (int x,y,i=1;i<=n;i++)read(x),read(y),kdt.insert(x,y);
	for (int opt,x,y;m--;)
		if (read(opt),read(x),read(y),opt==1)kdt.insert(x,y);
		else printf("%d\n",kdt.query(x,y));
	return 0;
}