Atcoder Regular Contest 063 D - Snuke's Coloring 2（单调栈+线段树）

本文主要是介绍Atcoder Regular Contest 063 D - Snuke's Coloring 2（单调栈+线段树），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷题面传送门 & Atcoder 题面传送门

好题一道。

一个很 trivial 的发现是答案等价于求一个周长最大的矩形，满足这个矩形内部（不含边界）没有其他点。

首先注意到一个性质：答案肯定不小于 \(2\max(H,W)+2\)，这是因为我们肯定可以框出一个 \(1\times\max(H,W)\) 的矩形，其内部肯定不会含其他点。考虑通过这个简单的性质我们可以得到什么。我们考虑将矩形从 \(x=\dfrac{W}{2},y=\dfrac{H}{2}\) 处劈成四个部分，那么可以发现，对于完全包含在四个部分之一的矩形，其周长最大不会超过 \(2(\dfrac{W}{2}+\dfrac{H}{2})=W+H<2\max(H,W)+2\)，也就是说，在最优决策方案中，\(x\) 轴和 \(y\) 轴中至少有一个方向是跨过中线的，这里我们不妨假设 \(y\) 轴跨过中线，\(x\) 轴跨过中线的情况用类似方法求一下即可。

我们考虑将所有点按 \(x\)​ 坐标从小到大排序然后枚举最终矩形的左右端点，或者说，横坐标等于左边界的点 \(i\)​ 和横坐标等于右边界的点 \(j\)​（由于我们已经将所有点按横坐标从小到大排序，因此必然有 \(i<j\)​），那么我们考虑纵坐标的范围，如果 \(j=i+1\)​ 那么显然纵坐标的范围可以是 \([0,H]\)​，该矩形对答案的贡献就是其周长 \(2(H+x_j-x_i)\)​，否则，我们考虑 \([i+1,j-1]\) 中的一个点 \(k\)，如果 \(2y_k\le H\)，那么由于我们强制要求其跨过中线，该矩形的下边界必须高于 \(y_k\)，否则 \(2y_k>H\)，该矩形的下边界也就应低于 \(y_k\)。这样我们可以得到矩形的上下边界，然后令答案对其取 \(\max\) 即可。

直接枚举是平方的，考虑优化。我们记 \(l_i,r_i\) 表示点 \(i\) 对矩形纵坐标范围的限制，具体来说如果 \(2y_i\le H\) 那么 \(l_i=y_i,r_i=H\)，否则 \(l_i=0,r_i=y_i\)，那么一组 \(i,j(i\le j-2)\) 对答案的贡献即为 \(2(x_j-x_i+(\max\limits_{k=i+1}^{j-1}r_k)-(\min\limits_{k=i+1}^{j-1}l_k))\)​，对 \(l,r\) 分别建一个单调栈处理掉即可。时间复杂度 \(n\log n\)。

using namespace fastio;
const int MAXN = 1e6;
const ll INFll = 0x3f3f3f3f3f3f3f3fll;
int W, H, n;
struct point {
	int x, y;
	friend bool operator < (point lhs, point rhs) {
		return lhs.x < rhs.x;
	}
} p[MAXN + 5];
struct node {int l, r; ll mx, lz;} s[MAXN * 4 + 5];
void pushup(int k) {s[k].mx = max(s[k << 1].mx, s[k << 1 | 1].mx);}
void build(int k, int l, int r) {
	s[k].l = l; s[k].r = r; s[k].mx = s[k].lz = 0; if (l == r) return;
	int mid = l + r >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r);
}
void tag(int k, ll v) {s[k].mx += v; s[k].lz += v;}
void pushdown(int k) {if (s[k].lz) tag(k << 1, s[k].lz), tag(k << 1 | 1, s[k].lz), s[k].lz = 0;}
void modify(int k, int l, int r, int v) {
	if (l > r) return;
	if (l <= s[k].l && s[k].r <= r) return tag(k, v), void();
	pushdown(k); int mid = s[k].l + s[k].r >> 1;
	if (r <= mid) modify(k << 1, l, r, v);
	else if (l > mid) modify(k << 1 | 1, l, r, v);
	else modify(k << 1, l, mid, v), modify(k << 1 | 1, mid + 1, r, v);
	pushup(k);
}
ll query(int k, int l, int r) {
	if (l > r) return -INFll;
	if (l <= s[k].l && s[k].r <= r) return s[k].mx;
	pushdown(k); int mid = s[k].l + s[k].r >> 1;
	if (r <= mid) return query(k << 1, l, r);
	else if (l > mid) return query(k << 1 | 1, l, r);
	else return max(query(k << 1, l, mid), query(k << 1 | 1, mid + 1, r));
}
stack<pii> up, dw;
void insup(int x, int p) {
	while (up.size() > 1 && up.top().fi > p) {
		pii pp = up.top(); up.pop();
		modify(1, up.top().se, pp.se - 1, -pp.fi);
	}
	modify(1, up.top().se, x - 1, p);
	up.push(mp(p, x));
}
void insdw(int x, int p) {
	while (dw.size() > 1 && dw.top().fi < p) {
		pii pp = dw.top(); dw.pop();
		modify(1, dw.top().se, pp.se - 1, pp.fi);
	}
	modify(1, dw.top().se, x - 1, -p);
	dw.push(mp(p, x));
}
ll calc() {
	sort(p + 1, p + n + 1);
	build(1, 0, n + 1); ll mx = 0;
	up.push(mp(0, 0)); dw.push(mp(0, 0));
	for (int i = 1; i <= n + 1; i++) {
		if (p[i - 1].y < H / 2) {
			insup(i - 1, H);
			insdw(i - 1, p[i - 1].y);
		} else {
			insup(i - 1, p[i - 1].y);
			insdw(i - 1, 0);
		}
		modify(1, i - 1, i - 1, -p[i - 1].x);
		chkmax(mx, query(1, 0, i - 2) + p[i].x);
		chkmax(mx, p[i].x - p[i - 1].x + H);
	}
	while (!up.empty()) up.pop();
	while (!dw.empty()) dw.pop();
	return mx;
}
int main() {
//	freopen("4-etzoob-244.in", "r", stdin);
//	freopen("4-etzoob-244.out", "w", stdout);
	read(n); read(W); read(H);
	for (int i = 1; i <= n; i++) read(p[i].x), read(p[i].y);
	p[n + 1] = {W, H}; ll res = calc();
	for (int i = 1; i <= n + 1; i++) swap(p[i].x, p[i].y);
	swap(W, H); chkmax(res, calc());
	printf("%lld\n", res << 1);
	return 0;
}

这篇关于Atcoder Regular Contest 063 D - Snuke's Coloring 2（单调栈+线段树）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！