Codeforces Gym 101471D Money for Nothing（2017 ACM-ICPC World Finals D题，决策单调性）

题目链接  2017 ACM-ICPC World Finals Problem D

（这题细节真的很多）

把所有的(pi,di)按横坐标升序排序。

对于某个点，若存在一个点在他左下角，那么这个点就是可以去掉的。

因为这个点的答案无论怎么优都劣于他左下角的这个点的答案。

 

对所有的(qj, ej)也同理。

然后就是一个分治的过程。

solve(L, R, l, r)表示对所有的在[L, R]中的买入点x都要找到一个最适合x的点y并更新答案。

首先对于某个买入点mid，在所有卖出点中找到横纵坐标都大于他的点的集合（是一段连续的点）

设这段点的下标范围为[ql, qr]

然后在这一段连续的点中找到最优的决策点Mid。

那么接下来递归下去就是solve(L, mid - 1, l, Mid)和solve(mid + 1, R, Mid, r)。

注意边界条件的特判。（也就是当横纵坐标都大于当前点的集合为空集时）

#include <bits/stdc++.h>

using namespace std;

#define	rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 5e5 + 10;

struct node{
	LL x, y;
	friend bool operator < (const node &a, const node &b){
		return a.x == b.x ? a.y < b.y : a.x < b.x;
	}
} a[N], b[N], wb[N];

LL x[N];
LL ans;
int n, m, px, py;

void solve(int l, int r, int st, int ed){
	if (l > r) return;
	int mid = (l + r) >> 1;
	LL mx = 0, vy = a[mid].y;
	int pos = 0;
	for (int i = upper_bound(x + st, x + ed + 1, a[mid].x) - x; i <= ed && vy < b[i].y; ++i){
		LL val = (b[i].x - a[mid].x) * (b[i].y - a[mid].y);
		if (val > mx) mx = val, pos = i;
	}

	ans = max(ans, mx);
	if (!pos){
		if (a[mid].y < b[st].y) solve(l, mid - 1, st, ed);
		if (a[mid].x < b[ed].x) solve(mid + 1, r, st, ed);
	}

	else{
		solve(l, mid - 1, st, pos);
		solve(mid + 1, r, pos, ed);
	}
}

int main(){

	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].y);
	rep(i, 1, m) scanf("%lld%lld", &wb[i].x, &wb[i].y);
	sort(a + 1, a + n + 1);
	sort(wb + 1, wb + m + 1);

	px = py = 1, b[1] = wb[m];
	

	rep(i, 2, n) if (a[i].y < a[px].y) a[++px] = a[i];
	dec(i, m - 1, 1) if (wb[i].y > b[py].y) b[++py] = wb[i];
	reverse(b + 1, b + py + 1);
	rep(i, 1, py) x[i] = b[i].x;

	ans = 0;
	solve(1, px, 1, py);
	printf("%lldn", ans);
	return 0;
}