【Luogu P4169】[Violet]天使玩偶/SJY摆棋子 / 题解

【Luogu P4169】[Violet]天使玩偶/SJY摆棋子 / 题解

Description

需要维护一个结构,要求支持以下2个操作。

  1. 向二位空间内插入一个点。
  2. 给出一个二维点,询问距离这个点曼哈顿距离最近的点的曼哈顿距离。

$n, m ≤ 3 × 10^5 , T = 3s$

Idea

本题可以使用 kd-tree 加上替罪羊树做到按题意模拟,但是我还不太会。

所以我们用 CDQ 分治解决这个问题。

对于每个要查询的点,二维空间被它分割成四个象限,我们只考虑第三象限的做法,然后不断翻转即可。

这样我们去掉了曼哈顿距离中的绝对值,将题目转化为一个简单的三维偏序问题:

对于一个询问 $(x, y)$,找到满足时间戳在其前且 $x_i \le x, y_i \le y$ 的点中 $x_i + y_i$​ 的最大值。

至于具体的实现,还是看代码吧。

Code

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define maxn 1000010
using namespace std;
int read(){
	int x=0,flag=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return x*flag;
}
void chkmin(int &x,int y){x=x<y?x:y;}
void chkmax(int &x,int y){x=x<y?y:x;}
struct Ask{
	int x,y,f,id;
	Ask(int a=0,int b=0,int c=0,int d=0){
		x=a,y=b,f=c,id=d;
	}
	bool operator < (const Ask &t) const{
		return x<=t.x;
	}
}p[maxn],q[maxn],a[maxn];
int n,m,lx,ly,lm,rm;
int c[maxn],ans[maxn];
void Clear(int x){
	while(x<=ly){
		if (c[x]) c[x]=0;
		else break;
		x+=(x&-x);
	}
}
int Query(int x){
	int r=0;
	while(x)
		chkmax(r,c[x]),
		x-=x&-x;
	return r;
}
void Modify(int x,int y){
	while(x<=ly)
		chkmax(c[x],y),
		x+=(x&-x);
}
void Delete(){
	lm=rm=m=0;
	for (int i=1;i<=n;++i)
		if (!p[i].f) chkmax(lm,p[i].x),chkmax(rm,p[i].y);
	for (int i=1;i<=n;++i)
		if (p[i].x<=lm&&p[i].y<=rm) q[++m]=p[i];
	for (int i=1;i<=m;++i) p[i]=q[i];
}
void CDQ(int l,int r){
	if (l==r) return;
	CDQ(l,mid),CDQ(mid+1,r);
	int j=l;
	for (int i=mid+1;i<=r;++i)
	if (!p[i].f){
		for (;j<=mid&&p[j].x<=p[i].x;++j)
			if (p[j].f) Modify(p[j].y,p[j].x+p[j].y);
		int tmp=Query(p[i].y);
		if (tmp) chkmin(ans[p[i].id],p[i].x+p[i].y-tmp);
	}
	for (int i=l;i<j;++i)
		if (p[i].f) Clear(p[i].y);
	merge(p+l,p+mid+1,p+mid+1,p+r+1,q+l);
	for (int i=l;i<=r;++i) p[i]=q[i];
}
int main(){
	n=read(),m=read();
	for (int i=1;i<=n;++i){
		int x=read()+1,y=read()+1;
		p[i]=Ask(x,y,1,i);
		chkmax(lx,x),chkmax(ly,y);
	}
	for (int i=1;i<=m;++i){
		int f=read(),x=read()+1,y=read()+1;
		++n,p[n]=Ask(x,y,f&1,n);
		chkmax(lx,x),chkmax(ly,y);
	}
	for (int i=1;i<=n;++i) a[i]=p[i];
	memset(ans,0x3f,sizeof(ans));
	++lx,++ly;
	Delete(),CDQ(1,m);
	for (int i=1;i<=n;++i)
		p[i]=a[i],p[i].x=lx-p[i].x;
	Delete(),CDQ(1,m);
	for (int i=1;i<=n;++i)
		p[i]=a[i],p[i].y=ly-p[i].y;
	Delete(),CDQ(1,m);
	for (int i=1;i<=n;++i)
		p[i]=a[i],p[i].x=lx-p[i].x,
		p[i].y=ly-p[i].y;
	Delete(),CDQ(1,m);
	for (int i=1;i<=n;++i)
		if (!a[i].f) printf("%d\n",ans[i]);
	return 0;
}