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;
}
上一篇:C#编程之AES加密(一)


下一篇:AtCoder Beginner Contest 232题解