AtcoderRegularContest063DSnuke'sColoring2（单调栈+线段树）

洛谷题面传送门 & 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\)​（由于我们已经将所有点按横坐标从小到大排序，因此必然有 \(iH\)，该矩形的下边界也就应低于 \(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 }
} 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

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 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 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;
}