ARC179E

Register_int · 2024-12-28 17:29:27 · 题解

我没有脑子，所以写了这个唐诗做法。

容易发现方案数至多为 2，因为最终的面积大小是固定的，至少一条边是固定的。

数区间问题考虑分治。对于分治中心右侧，可以对于每个前缀处理出 (x,y,dx,dy)，表示：若初始矩形边长为 (x,y)，那么这段前缀的矩形都能加上去，最终的效果是 (x,y)\to(x+dx,y+dy)。特别地，若对 x 或者 y 没有限制，则对应的值为 0。对于分治中心左侧，同样对于每个后缀预处理出 (x,y,dx,dy)。两侧的递推直接把当前矩形暴力并上去即可。又因为方案数不会超过 2，每个位置对应的 (x,y,dx,dy) 个数也不会超过 2，复杂度是对的。

统计答案时，由于分治中心右侧限制不断变紧，完全可以枚举左边二分找右边。时间复杂度 O(n\log^2 n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3e5 + 10;

struct node {
    ll x, y, dx, dy;
    node(ll x = 0, ll y = 0, ll dx = 0, ll dy = 0) : x(x), y(y), dx(dx), dy(dy) {};
}; vector<node> a[MAXN];

inline 
bool check(ll x, ll y, int k) {
    for (node p : a[k]) {
        if ((!p.x || p.x == x) && (!p.y || p.y == y)) return 1;
    }
    return 0;
}

inline 
int bound(ll x, ll y, int l, int r) {
    for (int mid; l < r; check(x, y, mid = l + r + 1 >> 1) ? l = mid : r = mid - 1);
    return l;
}

int n; ll x[MAXN], y[MAXN];

inline 
ll solve(int l, int r) {
    if (l == r) return 1;
    int mid = l + r >> 1; ll ans = 0;
    for (int i = l; i <= r; i++) a[i].clear();
    a[mid + 1].emplace_back(x[mid + 1], 0, 0, y[mid + 1]);
    a[mid + 1].emplace_back(0, y[mid + 1], x[mid + 1], 0);
    for (int i = mid + 2; i <= r; i++) {
        for (node p : a[i - 1]) {
            if (p.x && p.x + p.dx == x[i]) a[i].emplace_back(p.x, p.y, p.dx, p.dy + y[i]);
            else if (!p.x && x[i] > p.dx) a[i].emplace_back(x[i] - p.dx, p.y, p.dx, p.dy + y[i]);
            if (p.y && p.y + p.dy == y[i]) a[i].emplace_back(p.x, p.y, p.dx + x[i], p.dy);
            else if (!p.y && y[i] > p.dy) a[i].emplace_back(p.x, y[i] - p.dy, p.dx + x[i], p.dy);
        }
    }
    ans += bound(x[mid], y[mid], mid, r) - mid;
    a[mid].emplace_back(x[mid], 0, 0, y[mid]), a[mid].emplace_back(0, y[mid], x[mid], 0);
    for (int i = mid - 1, j; i >= l; i--) {
        j = mid;
        for (node p : a[i + 1]) {
            if ((!p.x || p.x == x[i]) && (!p.y || p.y == y[i])) {
                j = max(j, bound(x[i] + p.dx, y[i] + p.dy, mid, r));
            }
        }
        ans += j - mid;
        for (node p : a[i + 1]) {
            if (p.x && p.x == x[i]) {
                if (!p.y) a[i].emplace_back(p.x, p.y, p.dx, p.dy + y[i]);
                else if (p.y > y[i]) a[i].emplace_back(p.x, p.y - y[i], p.dx, p.dy + y[i]);
            } else if (!p.x && p.y > y[i]) a[i].emplace_back(x[i], p.y - y[i], p.dx, p.dy + y[i]);
            if (p.y && p.y == y[i]) {
                if (!p.x) a[i].emplace_back(p.x, p.y, p.dx + x[i], p.dy);
                else if (p.x > x[i]) a[i].emplace_back(p.x - x[i], p.y, p.dx + x[i], p.dy);
            } else if (!p.y && p.x > x[i]) a[i].emplace_back(p.x - x[i], y[i], p.dx + x[i], p.dy);
        }
    }
    return ans + solve(l, mid) + solve(mid + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &x[i], &y[i]);
    printf("%lld", solve(1, n));
}