P4169 [Violet]天使玩偶

两种操作：1.加入点（x,y); 2.查询距(x,y)最近的点的曼哈顿距离距离
思路:绝对值拆开通常可以取max,不过这里直接分类讨论4种情况，我们发现如果找\(i\)点左下点\(j\)\(（x_j<=x_i且y_j<=y_i)\)到\(i\)的最小距离：\(x_i-x_j+y_i-y_j=(x_i+y_i)-(x_j+y_j)\)

所以使距离最小即让\(x_j+y_j\)尽量大，我们发现这是个三维偏序问题：CDQ分治+树状数组

以上都是我能想到的，下面就是我菜鸡借鉴的：

其它三种情况怎么办？

题解告诉我们，同理！

其实有技巧的：我们找到x,y的范围上限（len），我们利用len-x,len-y这两种变换即可变幻出四种情况，无论i，j两个点开始在那个方向，都可以变化出j在i的所有方位(当然就包含了左下的情况）。

因此四次cdq即可。
注意:

1.树状数组下标不能存0，要把整体坐标+1

2.C要初始化为-inf而不是0因为在一个(x,y)左下角没有数的时候不应该更新答案

这个cdq的板子还是很优秀的，我没有卡任何常数直接过了

代码:

#include<bits/stdc++.h>

using namespace std;

const int N=1e7+5;

int inf=0x3f3f3f3f,C[N],n,m,tot=0,ans[N],len;

int lowbit(int u) {return u&(-u);}

void Update(int p,int d) {

	for(int i=p;i<=len;i+=lowbit(i)) C[i]=max(C[i],d);

}

int Ask(int p) {

	int mx=-inf;

	for(int i=p;i;i-=lowbit(i)) mx=max(mx,C[i]);

	return mx;

}

void Clear(int p) {

	for(int i=p;i<=len;i+=lowbit(i)) C[i]=-inf;

}

struct node {

	int opt,x,y,id;

}Q[N],a[N],t[N];

void CDQ(int l,int r) {

	if(l==r) return;

	int mid=(l+r)>>1;

	CDQ(l,mid),CDQ(mid+1,r);

	int i=l,j=mid+1,c=l;

	while(c<=r) {

		if((j>r)||(i<=mid&&Q[i].x<=Q[j].x)) {

			if(Q[i].opt==1) Update(Q[i].y,Q[i].x+Q[i].y);

			t[c++]=Q[i++];

		}

		else {

			if(Q[j].opt==2) ans[Q[j].id]=min(ans[Q[j].id],Q[j].x+Q[j].y-Ask(Q[j].y));

			t[c++]=Q[j++];

		}

	}

	for(int k=l;k<=mid;k++) if(Q[k].opt==1) Clear(Q[k].y);

	for(int k=l;k<=r;k++) Q[k]=t[k];

}

void _cdq(int fx,int fy) {

	for(int i=1;i<=tot;i++) {

		Q[i]=a[i];

		if(fx) Q[i].x=len-Q[i].x;

		if(fy) Q[i].y=len-Q[i].y;

	}

	CDQ(1,tot);

}

int main() {

	memset(ans,0x3f,sizeof(ans));

	memset(C,-0x3f,sizeof(C));

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) {

		++tot;

		scanf("%d%d",&a[tot].x,&a[tot].y); a[tot].opt=1,a[tot].id=tot;

		a[tot].x++,a[tot].y++;

		len=max(len,max(a[tot].x,a[tot].y));

	}

	for(int i=1;i<=m;i++) {

		tot++;

		scanf("%d%d%d",&a[tot].opt,&a[tot].x,&a[tot].y);

		a[tot].id=tot;

		a[tot].x++,a[tot].y++;

		len=max(len,max(a[tot].x,a[tot].y));

	}

	len++;

	_cdq(0,0),_cdq(0,1),_cdq(1,0),_cdq(1,1);

	for(int i=1;i<=tot;i++) {

		if(a[i].opt==2) {

			printf("%d\n",ans[i]);

		}

	}

	return 0;

}

巴特西

P4169 [Violet]天使玩偶

最新文章

热门文章