自动搬运

查看原文

来自洛谷，原作者为

	Sampson_YW 你弱归你弱，YW比你弱。

搬运于2025-08-24 22:25:52，当前版本为作者最后更新于2023-07-08 19:45:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先按 $l$ 从小到大排序。

最小化最大值，考虑二分答案。那么就要对当前二分的答案 $mid$ 构造一组方案。

我们从小到大依次枚举每个位置，并确定这个位置应该选哪个区间。

假设当前枚举到位置 $i$， 如果选择一个区间，那么其他与它有交的区间能填的位置不能超过 $i+mid$。

记 $f_x$ 表示区间 $x$ 最远能填哪里，记 $s_k = \sum_{x=1}^n[f_x=k]$。

我们找到最小的 $j$ 使得 $\sum_{k=i}^j s_k = j - i + 1$，显然所有 $f$ 值在 $[i, j]$ 之间的区间都必须填到 $[i,j]$ 中。

那么无解的条件就是存在一个 $p$ 使得 $\sum_{k=i}^p s_k > p - i + 1$。

我们贪心地选择区间，从 $f$ 值在 $[i,j]$ 之间的区间中选择 $r$ 最小的区间填到位置 $i$ 上，因为这样会使与位置 $i$ 相交的区间越少，受限制的区间数量就越少。

这样即可在 $O(n^2)$ 的时间内完成一次答案的构造。使用两棵线段树分别查找最小的 $j$ 和右端点最小的区间可优化至 $O(n\log n)$。

具体地，对于查找最小的 $j$，先将每个 $s_i$ 减一，那么对于一个 $i$，要找的 $j$ 就满足 $\sum_{k = i}^j s_k = 0$，线段树维护区间和与区间前缀和的最小值，线段树上二分即可做到 $O(n \log n)$。

对于找 $r$ 最小的区间，要满足 $f$ 值不超过 $j$。

由于序列按照 $l$ 排序，所以每次填一个区间 $[L_x, R_x]$，都会对 $l\leq R_x$ 的前缀产生限制。所以排序后序列的 $f$ 值是单调不降的。我们直接对这个前缀 chkmin 即可。那么会不会出现与 $[L_x, R_x]$ 无交的区间被 $\text{chkmin}$ 使得答案变劣呢？答案是不会的。

因为我们贪心地让 $r$ 小的尽量往前填，所以 $l \leq R_x$ 的区间，要么与 $[L_x, R_x]$ 有交，要么在之前就填过了。否则就会出现一个与 $[L_x, R_x]$ 无交且没有填的区间 $[L_y, R_y]$，满足 $L_y\leq L_x$，那么显然 $R_y\leq R_x$。由于 $[L_x,R_x]$ 能填且序列的 $f$ 值单调不降，所以 $f_y \leq f_x \leq j$，即 $[L_y, R_y]$ 也能填且更优，这与我们的贪心策略矛盾，所以不会出现无交且没填的区间。

第二棵线段树维护序列中没有被填过且 $r$ 最小的区间。

由于我们从小到大填，所以每个 $f$ 每个只会被 $\text{chkmin}$ 一次，用一个指针 $t$ 维护第一个还没被 $\text{chkmin}$ 的位置，设 $g_i$ 表示最后一个 $f=i$ 的位置。

对于要填的位置 $i$，我们用第一棵线段树找到 $j$，然后在第二棵线段树上查前缀 $g_j$ 中 $r$ 最小的区间 $[L_x, R_x]$，然后将 $x$ 删除，向后移动指针，更新 $f_t$ 并修改第一棵线段树，直到 $L_t>R_x$，此时更新 $g_{i + mid} = t - 1$。

总复杂度 $O(n\log^2 n)$。Code

此题弱化版：CF309E Sheep，$n\leq 2000$。