题解 AT2149 [ARC063D] すぬけ君の塗り絵 2 / Snuke's Coloring 2

· · 题解

怎么都是线段树做法啊，直接分治不好吗。

题意就是求一个周长最大的矩形，满足矩形内没有特殊点。

首先考虑大力分治。第一层分治枚举 x 轴上的中线，然后第二层枚举 y 轴的中线，问题就会转化为

这样的限制里面找周长最大的矩形。这里面有很多单调性可以利用。

我们可以观察到一个性质：答案矩形上方下方都至少有一个顶点在图中蓝色边框的顶点上。

那么我们去枚举矩形的右上角顶点，对于矩形左下角在蓝色顶点的情况，用一个单调队列维护左侧最优点；同时不要忘记矩形左下角在蓝色顶点的情况。具体的可以看代码。

枚举矩形左上角顶点同理，为了偷懒可以直接翻转过来再做一遍。于是我们可以做到 \mathcal O(n\log^2 n) 了。

然后还有一个重要性质，我们可以轻松找到一个 1\times H 或 W\times 1 的合法矩形，所以答案矩形周长一定大于 2\max(W,H)+2。这样的话该矩形就一定会跨过 x=\frac W 2 和 y=\frac H 2 两条直线中的一条。第一层分治只需要处理这两条直线作为中线就好了，复杂度降至 \mathcal O(n\log n)。

code

typedef long long LL;

const int N = 3e5 + 5;

struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
    friend bool operator <(const Point &a, const Point &b) {
        if (a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    }
};

int n, W, H, M, ans;
int up[N], dn[N], que[N];
Point a[N];

void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    // up,dn 分别表示上下边界
    int u = H, d = 0;
    for (int i = mid; i >= l; --i) {
        up[i] = u, dn[i] = d;
        if (a[i].y <= M) d = max(d, a[i].y);
        else u = min(u, a[i].y);
    }
    u = H, d = 0;
    for (int i = mid + 1; i <= r; ++i) {
        up[i] = u, dn[i] = d;
        if (a[i].y <= M) d = max(d, a[i].y);
        else u = min(u, a[i].y);
    }
#define val(_) (a[_].x + dn[_])
    int j = mid, sav = W;
    int ql = 1, qr = 0;
    for (int i = mid + 1; i <= r; ++i) {
        while (j >= l && up[j] >= up[i]) {
            while (ql <= qr && val(que[qr]) >= val(j)) --qr;
            que[++qr] = j;
            --j;
        }
        while (ql <= qr && dn[que[ql]] <= dn[i]) {
            sav = min(sav, a[que[ql]].x);
            ++ql;
        }
        ans = max(ans, a[i].x - sav + up[i] - dn[i]);
        if (ql <= qr) ans = max(ans, a[i].x + up[i] - val(que[ql]));
    }
    solve(l, mid), solve(mid + 1, r);
}

inline void main() {
    cin >> W >> H >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    sort(a+1, a+n+1);
    ans = max(W, H) + 1;

    M = H / 2;
    a[0] = Point(0, 0);
    a[n + 1] = Point(W, 0);
    solve(0, n + 1);
    reverse(a+1, a+n+1);
    for (int i = 1; i <= n; ++i) a[i].x = W - a[i].x;
    solve(0, n + 1);

    // 翻转
    swap(W, H);
    for (int i = 1; i <= n; ++i) swap(a[i].x, a[i].y);
    sort(a+1, a+n+1); // bug
    M = H / 2;
    a[0] = Point(0, 0);
    a[n + 1] = Point(W, 0);
    solve(0, n + 1);
    reverse(a+1, a+n+1);
    for (int i = 1; i <= n; ++i) a[i].x = W - a[i].x;
    solve(0, n + 1);

    cout << ans * 2 << '\n';
}