「Solution」ABC215.F.Dist Max 2

I’m good at making everything difficult!

提供一种线段树解法

link

分析

考试时确实没想到二分，结果整了个线段树解法恶心自己，二分已经在课上讲了，此处不再赘述。

如果我们把问题简化，考虑如下图两个点的位置关系。

如果当前两点的距离为$tx-x$,那么由题目可知$ty-y>tx-x$,移项得到$ty-tx>y-x$

如此，我们可以把分别维护两个点的横纵坐标差，变成维护一个点的横纵坐标之差。

那么若当前点为$(x_1, y_1)$,要使另一个点$(x_2, y_2)$ $(x_1\leq x_2,y_1\leq y_2)$与当前点之间的贡献为$x_2 - x_1$,必须满足的条件就是$y_1-x_1\leq y_2-x_2$.

然后我们可以定义一个$d=y-x$,每个点按$d$升序排序，对于当前点$(x_i, y_i)$能在横坐标上产生的最大贡献是$\max (x_i-x_j) | 1\leq j < i$.

那么只需要找到$[1,i-1]$中横坐标的最小值与当前点的横坐标做差即可。

这个地方就需要用到线段树。

但是会发现如此一来，我们只能统计到横纵坐标均小于等于当前点的点与当前点产生的贡献。

为了方便，我们假设所有点在第一象限，那么我们只需要按$x$轴、$y$轴分别将所有点翻转到另外三个象限再次统计答案即可。

如果是在纵坐标上产生贡献，统计方法与横坐标同理。

然后考场上没调出来。。。

后来发现是忘了初始化。。。

代码

#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

int n, cnt, ans, tx[MAXN], ty[MAXN];
map<int, int> h;
struct node {
	int x, y, d;
} a[MAXN];

int Abs (int x) {
	if (x < 0) return -x;
	else return x;
}

bool cmp1 (node p, node q) {
	if (p.d == q.d) {
		return p.x > q.x;
	} else return p.d < q.d;
}

bool cmp2 (node p, node q) {
	if (p.d == q.d) {
		return p.y > q.y;
	} else return p.d < q.d;
}

struct SegmentTree {
	int l, r, dat;
} s[MAXN * 4];

void push_up (int p) {
	s[p].dat = max (s[p << 1].dat, s[p << 1 | 1].dat);
}

void build (int p, int l, int r) {
	s[p].l = l, s[p].r = r;
	if (l == r) {
		s[p].dat = -INF;
		return;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	build (p << 1, l, mid);
	build (p << 1 | 1, mid + 1, r);
}

void update (int p, int x, int val) {
	if (s[p].l == s[p].r) {
		s[p].dat = val;
		return;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	if (x <= mid) update (p << 1, x, val);
	else update (p << 1 | 1, x, val);
	push_up (p);
}

int query (int p, int l, int r) {
	if (s[p].l >= l && s[p].r <= r) {
		return s[p].dat;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	int res = -INF;
	if (l <= mid) res = max (res, query (p << 1, l, r));
	if (r > mid) res = max (res, query (p << 1 | 1, l, r));
	return res;
}

void Find () {
	build (1, 1, n);
	for (int i = 1; i <= n; i++) a[i].d = a[i].x - a[i].y;
	sort (a + 1, a + 1 + n, cmp1);
	cnt = 0;
	h.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i].d != a[i - 1].d) {
			h[a[i].d] = ++cnt;
			update (1, cnt, a[i].x);
		}
	}
	for (int i = 1; i <= n; i++) {
		int hdi = h[a[i].d];
		ans = max (ans, query (1, 1, hdi) - a[i].x);
	}

	for (int i = 1; i <= n; i++) a[i].d = a[i].y - a[i].x;
	build (1, 1, n);
	sort (a + 1, a + 1 + n, cmp2);
	cnt = 0;
	h.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i].d != a[i - 1].d) {
			h[a[i].d] = ++cnt;
			update (1, cnt, a[i].y);
		}
	}
	for (int i = 1; i <= n; i++) {
		int hdi = h[a[i].d];
		ans = max (ans, query (1, 1, hdi) - a[i].y);
	}
}

void Forward () {
	for (int i = -1; i <= 1; i += 2) {
		for (int j = -1; j <= 1; j += 2) {
			for (int k = 1; k <= n; k++) {
				a[k].x = i * tx[k];
				a[k].y = j * ty[k];
//				printf ("%d %d\n", a[k].x, a[k].y);
			}
//			printf ("-------------\n");
			Find ();
		}
	}
}

int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf ("%d %d", &a[i].x, &a[i].y);
		tx[i] = a[i].x, ty[i] = a[i].y;
	}
	Forward ();
	printf ("%d\n", ans);
	return 0;
}