自动搬运

查看原文

来自洛谷，原作者为

	Cells 成功的秘诀只有™一个：加训。

搬运于2025-08-24 22:37:48，当前版本为作者最后更新于2025-07-28 16:38:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

很不错的一道题。

先看看数据范围，在 $O(n^3)$ 的时间复杂度内都是能接受的。

走构造这条路半天走不通，果断换方向。

根据题目的限制条件，每个位置都能处理出来它能够填的数的范围，这里可以直接暴力去做，时间复杂度 $O(m n ^ 2)$。

想到这一步，你只差临门一脚了，在看下面的题解之前我劝你再想想。

因为每个位置都对应一个数，所以我们只需要跑二分图最大匹配就可以了。

判断无解的话，你可以看最大匹配的数量是否等于 $n$，如果不相等说明有的位置没有值，不行。

当然，在这道题我们可以用匈牙利算法。

考虑优化 $O(m n^2)$ 建图。

发现对于一类区间（最大值和最小值），这里我举最大值的例子，我们按照 $v$ 降序排序，从前往后扫，在线段上的对应区间上直接推平成 $v$（因为每个位置的上界就是覆盖它的区间中最小的最大值，按照降序排序的原因），这样就得到了上界，下界同理，可以优化至 $O(m \log{m})$。

或者还是最大值的例子，按照将区间左端点排序，遍历每个位置，如果碰到左端点，则将 $v$ 加入堆中，这个位置的上界就是当前堆中的最小值，若是右端点（准确来说是右端点加一，因为右端点也是可以造成贡献的），利用 可删堆 删除，时间复杂度 $O(m \log{m})$。