P7013

· · 题解

首先按 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。