天使玩偶

题目描述

Ayu 在七年前曾经收到过一个天使玩偶,当时她把它当作时间囊埋在了地下。而七年后的今天,Ayu 却忘了她把天使玩偶埋在了哪里,所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系,而 Ayu 会不定时地记起可能在某个点埋下了天使玩偶;或者 Ayu 会询问你,假如她在 ($x,y$) ,那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动,所以在这个问题里我们定义两个点之间的距离为 dist(A,B)=|Ax-Bx|+|Ay-By|,其中 Ax 表示点 A的横坐标,其余类似。

第一行包含两个整数n和m ,在刚开始时,Ayu 已经知道有n个点可能埋着天使玩偶, 接下来 Ayu 要进行m 次操作
接下来n行,每行两个非负整数 ($x_i,y_i$),表示初始n个点的坐标。
再接下来m 行,每行三个非负整数 $t,x_i,y_i$。

如果$t=1$ ,则表示 Ayu 又回忆起了一个可能埋着玩偶的点 ($x_i,y_i$)
如果$t=2$ ,则表示 Ayu 询问如果她在点 ($x_i,y_i$) ,那么在已经回忆出来的点里,离她近的那个点有多远

对于每个$t=2$ 的询问,在单独的一行内输出该询问的结果。

$n,m$<=300 000
$x_i,y_i$<=1 000 000

代码

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
//这道题在luogu上不开O2我无能为力
inline void chkmax(int &x, int y){ if(y > x) x = y;}
inline void chkmin(int &x, int y){ if(y < x) x = y;}

struct ASK{
int type, x, y, id;
bool operator <(ASK a){
return a.x >= x;
//这个'<'是指内部<a
//没有理解清楚结果只拿了10分啊...
}
}a[1001000], b[1001000], now[1001000];//数组大小...

inline int lowbit(int x){ return x & (-x);}
void add(int k, int sum){ for(; k <= maxy; k += lowbit(k)) chkmax(c[k], sum);}
int coun(int k){ int t = 0; for(; k; k -= lowbit(k)) chkmax(t, c[k]); return t;}
inline void clear(int k){ for(; k <= maxy; k += lowbit(k)) if(c[k]) c[k] = 0;else return;}

void CDQ(int l, int r){
if(r <= l) return;
int mid = (l + r) >> 1;
CDQ(l, mid), CDQ(mid + 1, r);//保证数组是结果排序的
int it_l = l;
for(int i = mid + 1; i <= r; ++ i)if(b[i].type){//这大概也算个剪枝?
for(; it_l <= mid && b[it_l].x <= b[i].x; ++ it_l)//这个处理的还是很好的
if(!b[it_l].type) add(b[it_l].y, b[it_l].y + b[it_l].x);
//两点之间的曼哈顿距离其实就是xnow + ynow - x - y
//所以x + y为最大值(只考虑一个方向上的)时点(xnow,ynow)与点之间的曼哈顿距离就是最小的
//而且此处的b数组已经按照x的大小来进行排序了
//所以树状数组存储的就是下标为y时最大的y+x值
//好好理解
int nowmax = coun(b[i].y);
if(nowmax > 0) chkmin(ans[b[i].id], b[i].x + b[i].y - nowmax);

}
for(int i = l; i <= it_l; ++ i) if(!b[i].type) clear(b[i].y);
//树状数组要多次使用,所以务必要记得清空
merge(b + l, b + mid + 1, b + mid + 1, b + r + 1, now + l);
//普及一下归并排序的STL库
//merge(a + s1, a + e1, b + s2, b + e2, c + s3);
//所表示的意义是把a数组下标为[s1, e1)的区间与b数组下标为[s2, e2)的区间进行归并排序
//存储在c数组里,从下标s3开始
//然后这里注意我们重载了小于号,以x大小为标准进行排序
for(int i = l; i <= r; ++ i) b[i] = now[i];
}

void build(){
maxx = 0, maxy = 0, numnow = 0;
for(int i = n + 1; i <= m; ++ i){
if(b[i].type)
chkmax(maxx, b[i].x), chkmax(maxy, b[i].y);
}//找到询问坐标的最大x,y值,然后后面添加点的时候就有点类似于剪枝了
for(int i = 1; i <= m; ++ i){
if(b[i].x <= maxx && b[i].y <= maxy)
b[++ numnow] = b[i];
}
CDQ(1, numnow);
}

void solve(){
//这里的做法非常巧妙,只处理一个方向上的最近点曼哈顿距离,其余的转换后以同种方式处理
for(int i = 1; i <= m; ++ i) b[i] = a[i];
build();//左下
for(int i = 1; i <= m; ++ i) b[i] = a[i], b[i].x = xmax - b[i].x;
build();//右下
for(int i = 1; i <= m; ++ i) b[i] = a[i], b[i].y = ymax - b[i].y;
build();//左上
for(int i = 1; i <= m; ++ i) b[i] = a[i], b[i].x = xmax - b[i].x, b[i].y = ymax - b[i].y;
build();//右上
}

int main(){
n = read(), m = read() + n;
for(int i = 1; i <= n; ++ i) {
a[i] = ASK{0, read() + 1, read() + 1, 0};//树状数组不能处理0
chkmax(xmax, a[i].x), chkmax(ymax, a[i].y);
}
for(int i = n + 1; i <= m; ++ i) {
a[i] = ASK{read() - 1,read() + 1, read() + 1, i};
chkmax(xmax, a[i].x), chkmax(ymax, a[i].y);
}
memset(ans, 127, sizeof(ans));
++ xmax, ++ ymax;//同样因为树状数组
solve();
for(int i = n + 1; i <= m; ++ i) if(a[i].type) printf("%d\n", ans[i]);
return 0;
}

日常

元旦节放两天假耶!!!
回衡阳啦

昨天的元旦晚会很嗨啊
气氛还是挺热闹的
蒋文熙这个没良心的竟然关键时刻生病把工作全部丢给了我
不枉ccy和我顶着寒风细雨排练了那么那么久她还大方地借了汉服给我
话说我还是第一次穿汉服啊也是第一次梳那种发型
很高兴啊
"如果没有李白"
已经可以脱口而出了哈哈哈
没有遗憾啦
生物组的白雪公主新编好棒好棒啊
大家都演的超级好
然后就是为mcy打call!!!
实名控诉他现场唱的效果没有中午站在讲台上唱的好
然后hk的鸽子+纸短情长唱得我不自觉地姨母笑了啊
至于宝宝昨天发生的一系列奇妙的事情…
咳咳咳
我什么都不知道!
但是真的好甜好甜啊

今天去GZQ家吃饭啦
这一次他没怎么玩手机
表扬一下