P5423 [USACO19OPEN]Valleys P题解

· · 题解

P5423 [USACO19OPEN]Valleys P

作为一个蒟蒻，自己的做法可能会有些地方比较傻，欢迎大佬们指出并改进并嘲讽我这个蒟蒻。

Solution

首先，容易想到将所有的方格按照 b[i][j] 从小到大进行排序，并依次遍历。

为方便叙述，将满足区域内的任意格子的高度低于该区域边界上任意格子的高度的区域叫做“弱山谷”。

设遍历到的方格是 (i,j) ，将 (i,j) 和与它有边相连的方格中，b 值比 b[i][j] 小的合并到同一个集合内。

容易发现每次合并后的集合都是弱山谷。

所以只用判断该区域是否有洞即可。

首先计算将 (i,j) 加入弱山谷后，该弱山谷会增加多少个洞。

维护另一个并查集，将里面每一个方格都和与它有点相连的方格连边（这里的方格包括在 N \times N 方阵之外的无限高格子）。

将并查集中这个方格所连的边删去后，设与它有点相连的方格存在于 x 个不同的连通块中。

显然，这个问题的答案就是 \max(0, x - 1)。

但是从并查集中删边不好维护，考虑使用可撤销并查集。

按照把边删去的顺序反过来的顺序加边，删边直接撤销上一次操作即可。

再考虑将 (i,j) 加入弱山谷后，该弱山谷是否会减少洞。

维护 f[i][j] 表示与 (i,j) 有点相连的方格中，已经加入弱山谷的数量。

显然，如果 f[i][j] = 8，那么将 (i,j) 加入弱山谷后，该弱山谷的洞的数量会减少 1。

否则就不会减少。

每次操作后判断当前的弱山谷是否有洞，没有洞的话就加入答案。

说的可能有点难以理解，请大佬们原谅，把我的垃圾代码贴到下面。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 750;
const ll N = maxn + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll n, m, l, cnt, ans, a[N][N], f[N][N], fa[N * N], g[N * N], sz[N * N], fa1[N * N], sz1[N * N];
bool c[N][N];
ll dx[5] = {0, 1, -1, 0, 0};
ll dy[5] = {0, 0, 0, 1, -1};
struct nde{
    ll x, y, w;
}b[N * N];
bool cmp(nde p, nde q) {
    return p.w < q.w;
}
ll get_fa(ll x){
    if (fa[x] == x) {
        return x;
    }
    else {
        fa[x] = get_fa(fa[x]);
        return fa[x];
    }
}
void mrge(ll x, ll y) {
    ll p = get_fa(x), q = get_fa(y);
    if (p == q) {
        return;
    }
    fa[q] = p;
    g[p] += g[q];
    g[q] = 0;
    sz[p] += sz[q];
    sz[q] = 0;
}
ll slve(ll x, ll y) {
    return (x - 1) * n + y;
}
struct nde1 {
    ll x, y, u, v;
}B[N * N * 8];
ll slve1(ll x, ll y) {
    return x * (n + 2) + y + 1;
}
ll get_fa1(ll x) {
    if (fa1[x] == x) {
        return x;
    }
    else {
        return get_fa1(fa1[x]);
    }
}
void mrge1(ll x, ll y, ll u, ll v) {
    ll p = get_fa1(x), q = get_fa1(y);
    if (p == q) {
        return;
    }
    if (sz1[p] < sz1[q]) {
        swap(p, q);
    }
    ++cnt;
    B[cnt].x = q;
    B[cnt].y = fa1[q];
    B[cnt].u = u;
    B[cnt].v = v;
    fa1[q] = p;
    sz1[p] += sz1[q];
    sz1[q] = 0;
}
void re_mrge1() {
    fa1[B[cnt].x] = B[cnt].y;
    --cnt;
}
set<ll> st;
int main() {
    scanf("%lld", &n);
    l = 0;
    for (ll i = 1; i <= n; ++i) {
        for (ll j = 1; j <= n; ++j) {
            scanf("%lld", &a[i][j]);
            ++l;
            b[l].x = i;
            b[l].y = j;
            b[l].w = a[i][j];
        }
    }
    for (ll i = 1; i <= n; ++i) {
        for (ll j = 1; j <= n; ++j) {
            f[i][j] = 0;
            c[i][j] = 0;
        }
    }
    for (ll i = 1; i <= l; ++i) {
        fa[i] = i;
        g[i] = 0;
        sz[i] = 1;
    }
    for (ll i = 0; i <= n + 1; ++i) {
        a[0][i] = INF;
        a[n + 1][i] = INF;
    }
    for (ll i = 0; i <= n + 1; ++i) {
        a[i][0] = INF;
        a[i][n + 1] = INF;
    }
    // 预处理可撤销并查集
    for (ll i = 1; i <= (n + 2) * (n + 2); ++i) {
        fa1[i] = i;
        sz1[i] = 1;
    }
    for (ll i = 0; i <= n; ++i) {
        mrge1(slve1(0, i), slve1(0, i + 1), 0, 0);
        mrge1(slve1(n + 1, i), slve1(n + 1, i + 1), 0, 0);
    }
    for (ll i = 0; i <= n; ++i) {
        mrge1(slve1(i, 0), slve1(i + 1, 0), 0, 0);
        mrge1(slve1(i, n + 1), slve1(i + 1, n + 1), 0, 0);
    }
    sort(b + 1, b + l + 1, cmp);
    cnt = 0;
    for (ll p = l; p >= 1; --p) {
        ll x = b[p].x, y = b[p].y, w = b[p].w;
        for (ll i = -1; i <= 1; ++i) {
            for (ll j = -1; j <= 1; ++j) {
                ll xx = x + i, yy = y + j;
                if (!(xx == x && yy == y)) {
                    if (a[xx][yy] > a[x][y]) {
                        mrge1(slve1(x, y), slve1(xx, yy), x, y);
                    }
                }
            }
        }
    }
    ans = 0;
    for (ll p = 1; p <= l; ++p) {
        ll x = b[p].x, y = b[p].y, w = b[p].w;
        // 将该方格和与它有边相连的且高度小于它的合并到同一个集合
        for (ll i = 1; i <= 4; ++i) {
            ll xx = x + dx[i], yy = y + dy[i];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n) {
                if (a[xx][yy] < a[x][y]) {
                    mrge(slve(x, y), slve(xx, yy));
                }
            }
        }
        ll u = get_fa(slve(x, y));
        // 删除洞
        if (f[x][y] >= 8) {
            --g[u];
        }
        // 更新f值
        f[x][y] = 0;
        c[x][y] = 1;
        for (ll i = -1; i <= 1; ++i) {
            for (ll j = -1; j <= 1; ++j) {
                ll xx = x + i, yy = y + j;
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= n) {
                    if (!(xx == x && yy == y)) {
                        if (!c[xx][yy]) {
                            ++f[xx][yy];
                        }
                    }
                }
            }
        }
        // 统计增加了多少个洞
        while (cnt > 0 && (B[cnt].u == x && B[cnt].v == y)) {
            re_mrge1();
        }
        st.clear();
        for (ll i = -1; i <= 1; ++i) {
            for (ll j = -1; j <= 1; ++j) {
                ll xx = x + i, yy = y + j;
                if (!(xx == x && yy == y)) {
                    if (!c[xx][yy]) {
                        ll q = get_fa1(slve1(xx, yy));
                        st.insert(q);
                    }
                }
            }
        }
        if (ll(st.size()) >= 1) {
            g[u] += (ll(st.size()) - 1);
        }
        if (g[u] == 0) {
            ans += sz[u];
        }
    }
    printf("%lld", ans);
    return 0;
}