【题解】LuoGu2479：[SDOI2010]捉迷藏_p2479 [sdoi2010]捉迷藏-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/101787354

原题传送门
想到以前做过的 $p o j$ 的一道题 $s t a r s$ （好像是这么叫的）
考虑如何把绝对值扔掉
对于一个点 $(x, y)$ 和它左下的一个点 $(x 1, y 1) (x 1 < = x, y 1 < = y)$ ，那么两点曼哈顿距离: $x - x 1 + y - y 1 = (x + y) - (x 1 + y 1)$
如果只存在这一种情况，可以把点按照第一关键字 $x$ 第二关键字 $y$ 排序，先保证x升序情况下用树状数组维护每个点比 $y$ 小的点中 $(x + y)$ 的最大值/最小值求得答案

然后就是推广到四个方向（左上，左下，右上，右下）

$x > = x 1, y > = y 1 : d i s = (x + y) - (x 1 + y 1)$
$x > = x 1, y < y 1 : d i s = x - x 1 + y 1 - y = (x - y) - (x 1 - y 1)$
$x < = x 1, y > = y 1 : d i s = x 1 - x + y - y 1 = (- x + y) - (- x 1 + y 1)$
$x < = x 1, y < = y 1 : d i s = (- x - y) - (- x 1 - y 1)$

前两个正着跑，后两个倒着跑保证x的单调性
对于四种情况分别开2个树状数组维护 $m a x / m i n$

注意需要离散化
代码可读性很低，不信你看看
Code：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
struct point{
	int x, y, z;
}a[maxn], b[maxn];
int n, m, p, Min[maxn], Max[maxn], min1[maxn], min2[maxn], min3[maxn], min4[maxn], max1[maxn], max2[maxn], max3[maxn], max4[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

bool cmp(point x, point y){ return x.x == y.x ? x.y < y.y : x.x < y.x; }
bool cmp1(point x, point y){ return x.x < y.x; }
int lowbit(int x){return x & -x; }
void add1(int x, int y){ for (; x <= p; x += lowbit(x)) max1[x] = max(max1[x], y), min1[x] = min(min1[x], y); }
int query11(int x){ int sum = -1e9; for (; x; x -= lowbit(x)) sum = max(sum, max1[x]); return sum; }
int query12(int x){ int sum = 1e9; for (; x; x -= lowbit(x)) sum = min(sum, min1[x]); return sum; }
void add2(int x, int y){ for (; x; x -= lowbit(x)) max2[x] = max(max2[x], y), min2[x] = min(min2[x], y); }
int query21(int x){ int sum = -1e9; for (; x <= p; x += lowbit(x)) sum = max(sum, max2[x]); return sum; }
int query22(int x){ int sum = 1e9; for (; x <= p; x += lowbit(x)) sum = min(sum, min2[x]); return sum; }
void add3(int x, int y){ for (; x <= p; x += lowbit(x)) max3[x] = max(max3[x], y), min3[x] = min(min3[x], y); }
int query31(int x){ int sum = -1e9; for (; x; x -= lowbit(x)) sum = max(sum, max3[x]); return sum; }
int query32(int x){ int sum = 1e9; for (; x; x -= lowbit(x)) sum = min(sum, min3[x]); return sum; }
void add4(int x, int y){ for (; x; x -= lowbit(x)) max4[x] = max(max4[x], y), min4[x] = min(min4[x], y); }
int query41(int x){ int sum = -1e9; for (; x <= p; x += lowbit(x)) sum = max(sum, max4[x]); return sum; }
int query42(int x){ int sum = 1e9; for (; x <= p; x += lowbit(x)) sum = min(sum, min4[x]); return sum; }
void Add1(int i){ add1(a[i].z, a[i].x + a[i].y), add2(a[i].z, a[i].x - a[i].y); }
void Add2(int i){ add3(a[i].z, -a[i].x + a[i].y), add4(a[i].z, -a[i].x - a[i].y); }

int main(){
	n = read();
	for (int i = 1; i <= n; ++i) a[i] = (point){read(), read()}, b[++m] = (point){a[i].x, m}, b[++m] = (point){a[i].y, m}, Max[i] = -1e9, Min[i] = 1e9;
	sort(b + 1, b + 1 + m, cmp1);
	b[0].x = b[1].x + 1;
	for (int i = 1; i <= m; ++i){
		int x = b[i].x == b[i - 1].x ? p : ++p;
		if (b[i].y % 2 == 0) a[b[i].y >> 1].z = p;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= p; ++i) min1[i] = min2[i] = min3[i] = min4[i] = 1e9, max1[i] = max2[i] = max3[i] = max4[i] = -1e9;
	Add1(1); 
	for (int i = 2; i <= n; ++i){
		Max[i] = max(Max[i], max(a[i].x + a[i].y - query12(a[i].z), a[i].x - a[i].y - query22(a[i].z))),
		Min[i] = min(Min[i], min(a[i].x + a[i].y - query11(a[i].z), a[i].x - a[i].y - query21(a[i].z)));
		Add1(i);
	}
	Add2(n);
	for (int i = n - 1; i; --i){
		Max[i] = max(Max[i], max(-a[i].x + a[i].y - query32(a[i].z), -a[i].x - a[i].y - query42(a[i].z))),
		Min[i] = min(Min[i], min(-a[i].x + a[i].y - query31(a[i].z), -a[i].x - a[i].y - query41(a[i].z)));
		Add2(i);
	}
	int ans = 1e9;
	for (int i = 1; i <= n; ++i) ans = min(ans, Max[i] - Min[i]);
	printf("%d\n", ans);
	return 0;
}