Solution to block

· · 题解

前言

这题本来 \color{black}{w}\color{red}{ater\_tomato} 写的 std 结果被我爆踩了，所以就有了这篇文章。。

部分分大部分引用其原话，做法也不唯一，想看正解可以直接跳过。

Body

45 pts

Subtask 3

在该范围下，我们所需要求的是在全部高度已知的情况下的答案。我们考虑如何求 k 的最大值和最小值。

首先容易知道，给出的每一个看到的高度其实是这一列的最高的那一格的高度。即若 a_i=x，那么该列的 h_{max}=x（h 表示高度）。

最大值的情况很好考虑，对于从后往前数第 i 列的从左往右数第 j 个格子 (i,j)，只需要取其高度为 min(b_i,a_j) 。容易证明这是可行的方法中 k 最大的。

最小的值的情况略微麻烦一点点。我们考虑，如果存在一个 b_i=a_j，我们只需要在格子 (i,j) 放，就可以同时满足这两个值的要求。因此我们考虑先尽可能多的放这样的格子，再把仍然不满足的格子放满即可。显然的，在初步放的过程中，每一个 b_i 或 a_j 都是只能使用一次的，然后无法匹配的再暴力放置。

容易证明，从 MINN 至 MAXX 间的每一个值都是能够取到的。因此答案就是 MAXX-MINN+1。

然后我们考虑输出 0 的情况。显然，如果两边的最大值不相等，就是不可行的。

Subtask 2

对于这一种情况，显然 a_i \le 10，所以可以暴力枚举每一个 a_i=-1 的值，再乱搞即可。

Subtask 7

我们可以首先考虑输出 0 的情况。显然，如果 a_{max}>b_{max}，由于 b_i\ne-1 ，所以必然是不可行的。同时，如果其中某一组数据满足 a_i\ne-1，就成了 Subtask 3 的情况，此时若 b_{max}>a_{max}，也是不可行的。

然后我们考虑如果取 -1 的值。我们可以先将 b 从大到小进行排序，然后对于每一个 b_i 依次进行匹配，如果能够找到相同的，就直接匹配。否则，我们考虑是否需要取一个 -1 将之变为 b_i。

首先我们知道，在不考虑匹配的情况下，对于 a_i=-1，我们可以取 a_i=b_{max} 使尽可能多的可以该列格子能够放大值。接着我们考虑是否需要使 a_i=b_i。我们记贡献 w 为使最大值增加的值减去使最小值增加的值。当 a_i=b_i 时，初值为 0。如果取 a_i=b_{max}，初值就为 -b_{max}。接着我们遍历计算一下贡献，再将之进行比较。

至于为什么每一个 -1 的值一定在 a_i=b_i 和 a_i=b_{max} 中取呢？正确性证明如下:

首先考虑匹配的情况，a_i=b_i 初值一定会为 0，我们如果取更小的能够匹配的数，对于其他格子，能够放的高度肯定不会增加只会减少。

对于不匹配的情况，如果取 a_i=b_{max}-1，初值也为 b_{max}-1，但是我们知道至少存在一个 b_i=b_{max}。对于这一格，取 a_i=b_{max}-1 时的贡献为 b_{max}-1，而 a_i=b_{max} 的贡献为 b_{max}，这样两者就扯平了，而对于其他格子，显然 a_i 取越大，贡献不会减少而有可能增加。

注意，只要找到一次 a_i=b_{max} 的价值大于另一种，容易证明接下来所有的 a_i=b_i 价值也不会高于其，所以直接全部用 b_{max} 覆盖即可。

取完了之后，你需要使用 Subtask 3 中的方法求出最大值与最小值即可。

接着讲一下其他 Subtask：

对于 Subtask 5，你只需要考虑一个 b_i 的情况，帮助你从 b_i 的值上进行考虑，也有一些乱搞算法能过。

100 pts

主视图我们用列，左视图我们用行来表示。

首先我们可以知道，无论是左视图还是主视图，在每个视图中交换第 i、j 列 / 行 的高度（同一视图中）对答案是没有影响的，所以我们可以先对于序列 a、b 从小到大排个序，以方便我们处理。

因而现在我们有序列 a、b，a_1\le a_2\le \ldots \le a_n ,b_1\le b_2 \le \ldots \le b_m 。

判断无解的条件很简单，如果左视图最大高度小于主视图最大高度，或者主视图最大高度小于左视图最大高度且没有 a_i 等于 -1 的列，则输出 0。

即 

        if(a[n] > b[m]){
            puts("0");
            continue;
        }
        else if(a[1] != -1 && (a[n] < b[m])){
            puts("0");
            continue;
        }

然后我们想，对于主视图和左视图，如果高度都是确定的，那么对于第 i 列第 j 行的交汇处，如果不考虑最高的限制，其可取的范围即为 0 \sim min(a_i,b_j) 。由于行列都有最高限制，我们得在每行每列选择最大值处，固定它的高度，其余所有可活动高度的总和加上 1 就是我们所求的答案。

但是加之以主视图的高度的不确定性，我们不能单纯地枚举其可能性。由于左视图高度都是确定的，我们可以从左视图入手。从大到小枚举每一个高度 b_j 。由于三视图中每行列一定能看到最高高度，故我们钦定左视图第 j 行最高高度出现在主视图第 i 列中，届时就要用到一个匹配的思想。

我们定义

【1】 i ,j 合法 : b_j \le a_i 或 a_i = -1 , 即第 j 行最大高度可以出现在第 i 列中。

【2】 i 或 j 已匹配：第 i 列 \ 第 j 行 的最大高度位置已确定。

对于答案贡献我们对每一列一起处理，先预处理出 b 的前缀和 sum 。

显然如果两行的匹配位置同时为第 i 列，且还有第 k 列为匹配且合法，我们可以将其中一行的匹配位置挪到第 k 列中，因为如果 k 列最终闲置未匹配，则不得不自己再钦定最大值，而这样显然不会比挪到第 k 列更优秀。

对于那些 a_i \ne -1 的 i 来说，如果确定了匹配位置 j，那么这一列的贡献显然是 \sum_{b_l \le a_i}{b_l} 加上 \sum_{a_i \le b_l ,j \ne l}{b_j} 。

ans += sum[j - 1] + (m - j) * b[j];

如果 j 未匹配，那么只能委屈它放在已匹配的某 i 列中，贡献减少 b_j 。

ans -= b[j];

对于那些 a_i = -1 的 i 来说，如果确定了匹配位置 j，它的最高高度也未必是 b_j ，但一定大于等于 b_j 小于等于 b_m ，那么选择 b_j 和选择 b_{j+1} 的贡献差距为 sum_{j} + (m-j-1)\times b_{j+1} - b_j - sum_{j-1}- (m - j) \times b_j （这个时候 b_{j+1} 是确定的所以得减掉），整理一下是 (m-j-1)\times b_{j+1} - (m-j) \times b_j ,这个差的大小我们不清楚；然而对于选择 b_k 和 b_{k+1} （k > j）的贡献差为 b_k + (m-k-1) \times b_{k+1} - (m-k) \times b_k ,整理一下为 (m-k-1)\times (b_{k+1}-b_{k}) \ge 0 , 由此我们可以知道，如果最高高度不等于匹配位置高度的话，就一定等于 b_m，所以答案贡献为：

ans += max(sum[j - 1] + (m - j) * b[j], sum[m - 1] - b[j]);

对于那些未匹配的 i ，直接加上最大贡献就好了。

由于匹配时具有单调性，所以我们在枚举左视图行高时用 l , r 保存当前可匹配的下标范围即可。

最后不要忘了答案加一。

复杂度为 O(t \times n \times log_n) ，瓶颈在sort。

关键代码如下：

int j, l = 1, r = n;
        for(j = m; j >= 1; j--){
            while(l <= r && a[r] > b[j]){
                ans += sum[j] + (m - j - 1) * a[r];
                r--;
            }
            if(l <= r && a[r] == b[j]){
                r--;
                ans += sum[j - 1] + (m - j) * b[j];
            }
            else if(l <= r && a[l] == -1){
                ans += max(sum[j - 1] + (m - j) * b[j], sum[m - 1] - b[j]);
                l++;
            }
            else {
                ans -= b[j];
            }
        }
        while(l <= r){
            if(a[l] == -1){
                ans += sum[m - 1];
            }
            else {
                ans += (m - 1) * a[l];
            }
            l++;
        }
        printf("%lld\n", ans+1);