POI2018

luoguP5952

Problem Statement

Given an $n*m$ grid water tank, there is a wall of a certain height between adjacent cells.

The height of the walls and the water level do not exceed $H$. Question: How many water level situations are there?

Two situations are different if and only if there exists at least one cell whose water level height is different in the two situations (heights are integers).

Story

Today's story is the correct solution, reaching the pinnacle of life.

I don't know why this problem looks so familiar, I always feel like it was a problem I tried to solve when I first started learning OI$_{er}$ but couldn't.

Obviously, if we enumerate the water level from small to large, each cell will only be affected (merged) by the lowest wall. Then we enumerate the walls from small to large, and when merging two water areas, try to merge the two answers.

Let $f_i$ be the answer for water area $i$, and $g_i$ be the height of water area $i$. Initially, each cell is a water area with height $0$. If we merge water area $i$ and water area $j$ into water area $k$, and the height of the wall being merged is $h$, the transition is:

$$f_k=(f_i+h-g_i)*(f_j+h-g_j)\\ g_k=h.$$

(A cell $i$ raised from water level $g_i$ to $h$ has $h-g_i$ water level possibilities)

Summary: We find that this is a minimum spanning tree process, so we can directly build the graph and run minimum spanning tree, and count the answer when merging. (Why didn't I think of this back then)

Note the array size with this point numbering method

Wrote it a bit ugly, passed with oxygen optimization

#define MXNM (5000020)
#define XJQ (1000000007)

#include <stdio.h>

#include <queue>

int n, m, H;

int node(int i, int j) { return i * m + j; }

struct Edge {
    int u, v, w;
    bool operator<(const Edge E) const { return w > E.w; }
};

long long f[MXNM], g[MXNM];

std::priority_queue<Edge> edge;

int fa[MXNM];

int find(int x) { return (fa[x] == x) ? (x) : (fa[x] = find(fa[x])); }
void merge(int x, int y, long long h) { x = find(x), y = find(y), f[x] = ((f[x] + h - g[x]) * (f[y] + h - g[y])) % XJQ, g[x] = h, fa[y] = x; }

signed main() {
#ifndef ONLINE_JUDGE
    freopen("P5952.in", "r", stdin);
#endif

    scanf("%d%d%d", &n, &m, &H);

    for (int i = 1, j, w; i <= n; ++i)
        for (j = 1; j < m; ++j)
            scanf("%d", &w), edge.push(Edge{node(i, j), node(i, j + 1), w});
    for (int i = 1, j, w; i < n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &w), edge.push(Edge{node(i, j), node(i + 1, j), w});
    for (int i = 1, j; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            fa[node(i, j)] = node(i, j), f[node(i, j)] = 1;

    for (int i = n * m; i > 1; --i) {
        while ((!edge.empty()) && (find(edge.top().u) == find(edge.top().v))) edge.pop();
        if (!edge.empty()) merge(edge.top().u, edge.top().v, edge.top().w);
    }

    printf("%lld", (f[find(node(1, 1))] + H - g[find(node(1, 1))]) % XJQ);

    return 0;
}

Anyway, it's just a small easy problem, I don't know how it became a purple problem, I don't know how it was selected by Peking University master into miscellaneous problems.