「bzoj2716」「Violet 3」天使玩偶 - cdq分治三维偏序/K-D树 | Bill Yang's Blog

「bzoj2716」「Violet 3」天使玩偶 - cdq分治三维偏序/K-D树

题目大意

动态加点,询问距离一个点曼哈顿距离最近的点。


题目分析

考虑距离点$(x,y)$曼哈顿最近的点$(x0,y0)$。那么曼哈顿距离$\mid x-x0 \mid+\mid y-y0\mid$最小。

讨论四种情况,若点$(x0,y0)$在点$(x,y)$的左下方,则曼哈顿距离转为$x-x0+y-y0=(x+y)-(x0+y0)$。
那么我们就可以统计在$(x,y)$左下方的点中$(x0+y0)$最大的点。
动态加点->维护时间轴,再加上维护$x$、$y$轴,共维护三维偏序,使用cdq维护。

剩下的四种情况翻转一下坐标系即可。

关于三维偏序可以看这两篇文章:传送门1传送门2

本题还可以使用K-D树做,以后补坑。


代码

常数有点大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=2000005;
int Max=0,ans[maxn];
struct BIT {
int c[maxn];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=Max; i+=lowbit(i))c[i]=max(c[i],v);
}
void clear(int x) {
for(int i=x; i<=Max; i+=lowbit(i))c[i]=-0x7fffffff/2;
}
int sum(int x) {
int sum=-0x7fffffff/2;
for(int i=x; i>=1; i-=lowbit(i))sum=max(sum,c[i]);
return sum;
}
} bit;
struct Point {
int opt,x,y,t;
bool operator < (const Point& b) const { //x,y升序排列
return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&t<b.t);
}
} a[maxn],tmp[maxn];
int n,m;
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(a[i].t<=mid)tmp[lpos++]=a[i];
else tmp[rpos++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];
CDQBinary(Left,mid);
int j=Left;
for(int i=mid+1; i<=Right; i++) {
while(j<=mid&&a[j]<a[i]) {
if(a[j].opt==1)bit.add(a[j].y,a[j].x+a[j].y);
j++;
}
if(a[i].opt==2)ans[a[i].t]=min(ans[a[i].t],a[i].x+a[i].y-bit.sum(a[i].y));
}
for(int i=Left; i<=mid; i++)
if(a[i].opt==1)bit.clear(a[i].y);
CDQBinary(mid+1,Right);
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp);
int tot=0;
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i].x=Get_Int()+1;
a[i].y=Get_Int()+1;
a[i].t=i;
a[i].opt=1;
Max=max(Max,max(a[i].x,a[i].y)+1);
}
for(int i=1; i<=m; i++) {
a[n+i].opt=Get_Int();
a[n+i].x=Get_Int()+1;
a[n+i].y=Get_Int()+1;
a[n+i].t=n+i;
Max=max(Max,max(a[n+i].x,a[n+i].y)+1);
}
for(int i=1; i<=Max; i++)bit.c[i]=-0x7fffffff/2;
for(int i=1; i<=n+m; i++)ans[i]=0x7fffffff/2;
sort(a+1,a+n+m+1); //三象限
CDQBinary(1,n+m);
for(int i=1; i<=n+m; i++)a[i].x=Max-a[i].x; //四象限
sort(a+1,a+n+m+1);
CDQBinary(1,n+m);
for(int i=1; i<=n+m; i++)a[i].y=Max-a[i].y; //一象限
sort(a+1,a+n+m+1);
CDQBinary(1,n+m);
for(int i=1; i<=n+m; i++)a[i].x=Max-a[i].x; //二象限
sort(a+1,a+n+m+1);
CDQBinary(1,n+m);
for(int i=n+1; i<=n+m; i++)
if(ans[i]<0x7fffffff/2)printf("%d\n",ans[i]);
return 0;
}

0%