[USACO08JAN] Artificial Lake G

题意

给出 N 个从左到右排列的平台，每个平台有宽度 W_i 和高度 H_i，且所有高度互不相同。

从全局最低的平台开始，以每分钟 1 单位体积的速度向湖中注水。

要求对每个平台输出：它的平台顶从哪个时刻开始，与水面的距离至少为 1，也就是它第一次被完全淹没的时刻。

思路

先看一个慢版对照：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int n;
long long w[MAXN], h[MAXN];
int left_son[MAXN], right_son[MAXN], parent_node[MAXN];
long long sub_width[MAXN];
long long ans[MAXN];

int build_tree(int l, int r) {
    if (l > r) {
        return 0;
    }

    int root = l;
    for (int i = l + 1; i <= r; i++) {
        if (h[i] > h[root]) {
            root = i;
        }
    }

    left_son[root] = build_tree(l, root - 1);
    right_son[root] = build_tree(root + 1, r);
    if (left_son[root] != 0) {
        parent_node[left_son[root]] = root;
    }
    if (right_son[root] != 0) {
        parent_node[right_son[root]] = root;
    }
    return root;
}

long long dfs_width(int u) {
    if (u == 0) {
        return 0;
    }
    sub_width[u] = w[u] + dfs_width(left_son[u]) + dfs_width(right_son[u]);
    return sub_width[u];
}

// 慢速版本仍然使用同样的递归水位模型，只是建树改成 O(n^2)。
long long flood_subtree(int u, int side, long long cap, long long start) {
    if (u == 0) {
        return 0;
    }

    long long first_cost = 0;
    long long second_cost = 0;
    long long reach_top_time = start;

    if (side == 0) {
        first_cost = flood_subtree(left_son[u], 0, h[u], start);
        reach_top_time = start + first_cost;
        second_cost = flood_subtree(right_son[u], 0, h[u], reach_top_time);
    } else {
        first_cost = flood_subtree(right_son[u], 1, h[u], start);
        reach_top_time = start + first_cost;
        second_cost = flood_subtree(left_son[u], 1, h[u], reach_top_time);
    }

    ans[u] = reach_top_time + second_cost + sub_width[u];
    return first_cost + second_cost + sub_width[u] * (cap - h[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> h[i];
        left_son[i] = right_son[i] = parent_node[i] = 0;
        sub_width[i] = ans[i] = 0;
    }

    int root = build_tree(1, n);
    dfs_width(root);

    int source = 1;
    for (int i = 2; i <= n; i++) {
        if (h[i] < h[source]) {
            source = i;
        }
    }

    long long active_width = w[source];
    long long current_time = 0;
    ans[source] = active_width;

    int cur = source;
    while (parent_node[cur] != 0) {
        int p = parent_node[cur];

        current_time += active_width * (h[p] - h[cur]);

        int sibling = 0;
        long long sibling_cost = 0;
        if (left_son[p] == cur) {
            sibling = right_son[p];
            sibling_cost = flood_subtree(sibling, 0, h[p], current_time);
        } else {
            sibling = left_son[p];
            sibling_cost = flood_subtree(sibling, 1, h[p], current_time);
        }

        current_time += sibling_cost;
        active_width += w[p] + sub_width[sibling];
        ans[p] = current_time + active_width;

        cur = p;
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

brute.cpp 并不是逐分钟模拟，而是和正式解使用同一个递推模型，只不过它在每个区间里暴力找最高平台建树，所以只适合小数据验证。

这题真正的关键观察是：

某个平台要被淹没，左右更低的平台区域必须先灌到它的高度
所以一个区间里的最高平台，一定会比这个区间里的其它平台更晚被淹没

这正好对应一棵最大笛卡尔树：

中序遍历顺序等于原平台顺序
父节点高度严格高于子节点

在这棵树里，一个节点的整棵子树就对应一个完整盆地区间。

递归灌水时，可以这样理解：

如果从某个子树的一侧开始灌水，那么过程一定是：

先把这一侧的较低部分灌到根节点高度
水第一次碰到根顶
再从根顶流向另一侧，把另一侧也灌到根高度
最后整棵子树作为一个整体继续上涨

于是根节点被淹没的时刻可以递推出来：

先算“水第一次碰到根顶”的时刻
再加上另一侧被灌到根高度所需时间
再加上整棵子树整体上涨 1 所需时间

最后这一项，正好就是整棵子树的总宽度。

正式解的优化点在于：

用单调栈在线性时间建出最大笛卡尔树

之后所有递推都在线性规模内完成。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long w[MAXN], h[MAXN];
int left_son[MAXN], right_son[MAXN], parent_node[MAXN];
int stk[MAXN], top_idx;
long long sub_width[MAXN];
long long ans[MAXN];

void build_cartesian_tree() {
    top_idx = 0;

    for (int i = 1; i <= n; i++) {
        left_son[i] = right_son[i] = parent_node[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        int last = 0;
        while (top_idx > 0 && h[stk[top_idx]] < h[i]) {
            last = stk[top_idx];
            top_idx--;
        }
        if (top_idx > 0) {
            right_son[stk[top_idx]] = i;
            parent_node[i] = stk[top_idx];
        }
        if (last != 0) {
            left_son[i] = last;
            parent_node[last] = i;
        }
        stk[++top_idx] = i;
    }
}

long long dfs_width(int u) {
    if (u == 0) {
        return 0;
    }
    sub_width[u] = w[u] + dfs_width(left_son[u]) + dfs_width(right_son[u]);
    return sub_width[u];
}

// 在一个子树中灌水：
// side=0 表示水从这个子树的左边进入，side=1 表示从右边进入。
// cap 表示外侧“挡板”的高度，且保证 cap > h[u]。
// start 表示开始往这个子树里灌水的时刻。
// 返回把整个子树都灌到高度 cap 所需的总时间。
long long flood_subtree(int u, int side, long long cap, long long start) {
    if (u == 0) {
        return 0;
    }

    long long first_cost = 0;
    long long second_cost = 0;
    long long reach_top_time = start;

    if (side == 0) {
        // 从左边进来，要先把左子树灌到当前根的高度，才能第一次碰到根顶。
        first_cost = flood_subtree(left_son[u], 0, h[u], start);
        reach_top_time = start + first_cost;

        // 根顶被碰到后，水会从根顶继续流向右子树。
        second_cost = flood_subtree(right_son[u], 0, h[u], reach_top_time);
    } else {
        // 从右边进入时完全对称。
        first_cost = flood_subtree(right_son[u], 1, h[u], start);
        reach_top_time = start + first_cost;
        second_cost = flood_subtree(left_son[u], 1, h[u], reach_top_time);
    }

    // 当两侧都被灌到 h[u] 以后，整棵子树才会作为一个整体继续上升。
    ans[u] = reach_top_time + second_cost + sub_width[u];

    return first_cost + second_cost + sub_width[u] * (cap - h[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> h[i];
    }

    build_cartesian_tree();

    int root = stk[1];
    int source = 1;
    for (int i = 2; i <= n; i++) {
        if (h[i] < h[source]) {
            source = i;
        }
    }

    dfs_width(root);

    long long active_width = w[source];
    long long current_time = 0;
    ans[source] = active_width;

    int cur = source;
    while (parent_node[cur] != 0) {
        int p = parent_node[cur];

        // 先把当前已经连通的水体整体抬到父节点的高度。
        current_time += active_width * (h[p] - h[cur]);

        int sibling = 0;
        long long sibling_cost = 0;

        if (left_son[p] == cur) {
            sibling = right_son[p];
            sibling_cost = flood_subtree(sibling, 0, h[p], current_time);
        } else {
            sibling = left_son[p];
            sibling_cost = flood_subtree(sibling, 1, h[p], current_time);
        }

        current_time += sibling_cost;
        active_width += w[p] + sub_width[sibling];

        ans[p] = current_time + active_width;
        cur = p;
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

复杂度

单调栈建树、统计子树宽度、递归计算答案都只会线性处理每个平台常数次。

所以总时间复杂度是：

$O(N)$

空间复杂度是：

$O(N)$

总结

这题最难的不是实现，而是把“灌水过程”重新看成一棵树上的递推关系。

一旦想到：

区间最高点最后被淹没
可以用最大笛卡尔树表示包含关系

后面的公式推导就顺了。

[USACO08JAN] Artificial Lake G

目录

题意

思路

代码

复杂度

总结