JOISC 2017 D - 洛谷保存站

神题，模拟赛考到，不会，遂题解诞生。

读完题目，发现等价于给出若干 $[l_i,r_i],c_i$，需要将 $c_i$ 分为 $k,c_i-k$ 两部分加到 $[l_i,r_i]$ 亦或 $[1,l_i)\cup (r_i,n]$，要求最小化最后每个位置的值的最大值。

可以考虑一个调整法的思路，我们先假定全部分给 $[l_i,r_i]$，得到当前的解 $p_i$，同时将 $c_i$ 拆分为 $c_i$ 个 $l_i,r_i$ 相同且 $c_i=1$ 的询问。

问题就变成给出一个集合，元素为区间，而我们现在需要从中找到一个最优秀的子集 $S$，使得将 $\forall [l_i,r_i]\in S$ 拆为 $[1,l_i-1],[r_i+1,n]$ 后最大值最小。

我们称这个拆解的过程为“反转”。

我们设这个拆分后每个位置上的值是 $q_i$，那么会发现一些性质。

## 性质零

设最优答案为 $ans$，则我们声称 $[ans,\sum c]$ 都是存在方案的。

证明是显然的， $i$ 的一个没有覆盖最大值的区间覆盖过去就好了。

## 性质一

可以发现，若 $I_1,I_2\in S$，且 $I_1\cap I_2=\varnothing$，则 $S$ 并非最优。

证明：考虑此时我们**不反转** $I_1,I_2$，则会让 $q$ 产生如下变化：

1. $i\in I_1\cup I_2,q_i\leftarrow q_i$
2. $i\notin I_1\cup I_2,q_i\leftarrow q_i-2$

这样的变化一定不劣。

由此可以得到：**一定存在最优集合 $S$，满足 $S$ 里所有区间的交集不为空**。

形式化地，有：$\max_{[l_i,r_i]\in S}l_i\le \min_{[l_i,r_i]\in S}r_i$

下面我们称 $I=[\max_{[l_i,r_i]\in S},l_i,\min_{[l_i,r_i]\in S},r_i]$

----

现在我们来考虑在多项式复杂度内解决本问题。

设 $z_i=\sum_{[l_i,r_i]]\in S}[i\in [l_i,r_i]]$，也就是包含它的元素个数。

那么有 $q_i=p_i+(|S|-z_i)-z_i=p_i-2z_i+|S|$。

设某个 $t\in I$，则 $z_t=|S|$。

考虑二分答案，设当前二分答案为 $limit$，如果合法的充要条件是什么呢？

也就是 $\exists S,t,\max q_i\le limit$。

注意到我们在计算过程中只关心 $|S|$，也就是 $z_t$，不妨枚举 $t,z_t$，那么会有：$\max (p_i-2z_i+z_t)\le limit\implies z_i\ge \lceil\frac{p_i+z_t-limit}{2}\rceil$。

考虑构造这样一个 $S$，可以想到一个显然正确的贪心算法：依次扫描 $i:1\to t$，并开一个优先队列，维护当前待使用的所有区间，按照 $r$ 排序，当前发现 $z_i$ 不足，那么就贪心地选大的 $r$ 填上去。

最后再判断 $t+1\to n$ 的 $z$ 是否符合即可。

复杂度 $O(n^2m\log m\log V)$。

----

注意到复杂度主要开销是 $(t,z_t)$ 的枚举。

## 性质二

我们断言，如果最优解不是 $S=\varnothing$，那么一定有 $\exists t,S,\max_{i\in I}q_i\ge \max_{i}q_i-1,\max_{i}q_i\le limit$。

考虑如下当 $\max_{i\in I} q_i<\max_iq_i-1$ 时对 $S$ 的调整：

以下操作只要 $S$ 不为空且条件不满足持续进行。

1. $I\in S$，直接删除 $I$，那么有 $\forall i\in I,q_i'\leftarrow q_i+1,\forall i\notin I,q'_i\leftarrow q_i-1$，导致两者差距缩小 $2$。
2. 否则考虑取到 $I$ 的两个集合，也就是 $r_{\min},l_{\max}$ 所在的两个区间 $A,B$，将其删去，那么有 $\forall i\in I,q_i'\leftarrow q_i+2$，其余 $q_i$ 不变，也可以将差距缩小 $2$。

可以发现操作始终可以进行，因此最终必然可以操作到满足条件，或者 $S=\varnothing$。

注意到我们**可以钦定 $t$ 为取到 $\max_{i\in I}q_i$ 的 $i$，因为 $I$ 中的点对于 $S$ 这个方案而言是等价的**。

由此，我们可以知道 $\max_{i\in I}q_i=q_t\ge \max_{i}q_i-1$，而由性质零和构造方法，只要有解，那么我们就可以强化为构造出一个正好答案是 $\max_iq_i=limit$ 的解，因此 $limit\ge q_t=p_t-z_t\ge limit-1$，因此对于 $t$，我们仅需枚举 $p-limit(+1)$ 这两个即可。

复杂度降到 $O(n^2\log m\log V)$。

## 性质三

我们断言，如果最优解 $S\neq \varnothing$，那么一定是有某个最优的 $S,t$，满足 $p_t=\max p_i$。

注意到这个 $t$ 同样取到了 $\max_{i\in I}q_i$，因此有：

$$q_t=p_t-z_t\ge \max_iq_i-1\ge \max_i(p_i-2z_i+z_t)-1\ge \max(p_i-z_t+[i\notin I])-1$$

这推出 $p_t\ge \max(p_i+[i\notin I])-1\implies p_t=\max p_i$。

## 性质四

更强于性质三的，我们给出，如果最优解不是 $S=\varnothing$，那么存在最优解 $S$，任意 $\lbrace t|p_t=\max_{i}p_i\rbrace\subseteq I$ 。

设一个 $x,p_x=\max p_i$，则 $q_x=p_x+|S|-2z_x\le ans\le p_x-|S|+1\implies 2|S|-2z_x\le 1$。

由于左边是偶数且非负，所以只能取到 $z_x=|S|$，因此 $x\in I$。

综合各个性质，我们仅需 $2$ 次贪心算法就可以判断了。

$O(n\log m\log V)$ 解决问题。

正在渲染内容...