Description
需要维护一个结构,要求支持以下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;
}